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
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)
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,
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 ...
The solution provides two short and elegant proofs. Divisors and relative prime functions are provided.