Explore BrainMass

Divisors and relative primes

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,


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.