Divisors and relative primes

ONLY RESPOND IF THERE IS A

mistake

something is unclear

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:

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



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.