Sunday, May 15, 2005

Coprime Numbers: More Results

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