1. Mathematics
2. Discrete Math
3. 26510

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,