Explore BrainMass

Explore BrainMass

    Divisors and relative primes

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    Let a be an integer. Prove that 2a + 1 and a^2+ 1 are relatively prime.
    ( relative primes are numbers that their largest common divisor is 1).

    a. mistake
    b. something is unclear
    c. proof is correct, but solved incorrectly (does not follow instructions) Exm. Instruction says proof by induction, but instead solution is a proof by contradiction.

    Please use words to describe your proof.


    Let a be an integer. Prove that 2a + 1 and + 1 are relatively prime.

    Notation: a | b means "a divides b" (evenly) It is understood that a <= b

    To prove this, we need a lemma (sub-proof).

    if d | a and d | b then d | (a + b)

    If d | a then a = kd. Similarly b = md

    a + b = kd + md = (k + m)d = nd

    Since a + b is a multiple of d then d | (a + b)

    In English

    d | a means that a is a multiple of d, so we write it as in integer multiple of d

    When adding the two, we notice that d factors out from both terms and k + m is another integer n.

    The last line reverses the step that we made in the first.

    Corollary (which we will actually use)

    (If one of the two terms is divisible by d but the other is not, then there sum is not divisible by d.)

    Proof by contradiction

    The first line assumes that d does not divide into a but does divide into b and a + b. We apply the definition to d | b and d | (a + b) and manipulate algebraically to get a=md. Therefore d | a. But we stated beforehand that d does not divide into a, hence a contradiction (Symbolically represented by the opposing arrows). Since we made the original statement that d | (a + b) and we reached a contradiction, then we know that our assertion was false.

    Definition: Two numbers are said to be relatively prime if they do not have any common factors. Example 8=2*2*2 and 15=3*5 are relatively prime

    The actual proof.

    First, we note that

    Let , d is prime > 2 (2a+1 is an odd number and hence not divisible by 2). If we can show that then we have proven that they are relatively prime because any d that divides into 2a+1 will not divide into 4a2 + 1 and therefore have no common factors other than 1.

    But because d > 2 and by definition, d | a implies that d < a, therefore and by our corollary,

    © BrainMass Inc. brainmass.com May 24, 2023, 1:33 pm ad1c9bdddf


    Solution Preview

    See Attached

    Let's assume that k and that k is a divisor of both and such that:

    Where p and q are integers.


    Since p and q(2a-1) are integers, the only way the last equation can be true is if k value is either 1 or ...

    Solution Summary

    The solution provides two short and elegant proofs. Divisors and relative prime functions are provided.