Explore BrainMass

Explore BrainMass

    Divisors and relative primes

    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).

    ONLY RESPOND IF THERE IS A
    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.

    Problem:

    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 March 4, 2021, 6:03 pm ad1c9bdddf
    https://brainmass.com/math/discrete-math/divisors-relative-primes-26510

    Attachments

    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.

    Now,

    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.

    $2.19

    ADVERTISEMENT