In this blog, I will review some basic results regarding coprime numbers.
Lemma 1: p,q coprime -> pq, p2 - q2 are coprime.
(1) Assume gcd(pq,p2 - q2) = d and d is greater than 1
(2) So, there is some prime P which divides d [Fundamental Theorem of Artihmetic]
(3) Since d divides pq. P either divides p or q. [Euclid's Lemma]
(4) Let's assume P divides p and the same argument will apply if it divides q. So that, there exists R such that p = PR.
(5) Since d divides p2 - q2, there exists a value Q such that p2 - q2 = PQ
(6) This means that q2 = p2 - PQ = (PR)2 - PQ = P(PR2 - Q).
(7) But this means that P divides q by Euclid's Lemma which is a contradiction since P also divides p. [Because gcd(p,q)=1]
(8) Therefore, we reject our assumption.
QED
Lemma 2: p,q are relatively prime and are of different parity (one is odd, one is even), then p + q, p - q are relatively prime.
(1) Assume that gcd(p+q,p-q) = d and d is greater than 1.
(2) Then there exists a prime x which divides d. [Fundamental Theorem of Arithmetic]
(3) We know that this x is odd since p+q and p-q are odd. [Since they are of different parity]
(4) Now x divideds 2p since 2p = (p + q) + (p - q) which means x divides p. [By Euclid's Lemma Since x is odd]
(5) Likewise x divides 2q since 2q = (p + q) - (p - q) = p + q - p + q which means x divides q. [Same reason as above]
(6) But this is a contradiction since p,q are relatively prime.
QED
Lemma 3: if S2 = P2 + Q2 and P2 = T2 + Q2, then Q,S,T are relatively prime.
(1) We can assume that S,P,Q are relatively prime and P,T,Q are relatively prime. [See Lemma 1, here for details]
(2) We can also assume that S,P are odd which means that Q is even and that T is odd. [See details above]
(3) From the two equations, we can derive that:
S2 = T2 + 2Q2
(4) Now we need only prove that any factor that divides 2 values, will divide the third.
Case I: f divides S,Q
(a) There exists s,q such that S = fs, Q = fq
(b) T2 = S2 - 2Q2 = f2 [ s2 - 2q2 ]
(c) Which means that f divides T [See here.]
Case II: f divides T,Q
(a) We can use the same argument as Case I.
Case III: f divides S,T
(a) There exists s,t such that S = fs, T = ft
(b) 2Q2 = f2[ s2 - t2 ]
(c) Since S,T are odd, f must be odd and s,t must be odd.
(d) Then, s2 - t2 must be even.
(e) Then, there exists u such that 2u = s2 - t2
(f) So, we have:
2Q2 = (2)u(f2)
(g) And canceling out the 2s gives us:
Q2 = f2u
QED
Lemma 4: S,T relatively prime, both odd, 2u = S - T, 2v = S + T, then u,v are relatively prime.
(1) Assume f divides u,v such that u = fU, v = fV.
(2) The f divides S
S - T + S + T = 2S = 2u + 2v = 2f(U + V)
(3) And f divides T
S + T - (S - T) = 2T = 2v - 2u = 2f(V - U)l.
(4) This contradicts our S,T beings coprime so we reject our assumption.
QED
