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.


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.


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

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.



Oscar Rojas said...

Hi Larry,

I think that in Lemma 3, the assumption 1 (about some of the numbers being relative primes) should be part of the hypothesis.

In fact the Lemma does not hold if that assumption is not satisfied.

The proper assumption must be made in the part of fermat's one proof that is using the Lemma 3.

Since Lemma 3 is only used in that proof, then one could say that it is irrelevant where do you place the assumption... but, for pure formalism...

Larry Freeman said...

Hi Oscar,

The assumption is justified by the proof in Lemma 1 in the link.

Since we can reduce any solution to x^n + y^n = z^n to a form where x,y,z are coprime (see Lemma 1, here), we can assume that S,P,Q and P,T,Q are relatively prime because if they weren't, then we could still find a form that was.


Oscar Rojas said...

Thanks Larry.

I am sorry; I failed to state more clear my comment. I will try to do it better:

I agree that the assumption is justified... but it is justified in the context outside the lemma. If you take the lemma out of that context, it is not true as written.

The only fact in the hypothesis is that the numbers satisfy the equations, and that simple fact is not sufficient to derive the conclusion. If you take another set of numbers that are multiples of the originals, the new set still satisfy the unrestricted hypothesis but obviously they do not satisfy the conclusion.

So, I am not against the assumption, I am against using it as part of the proof of the lemma.
To save the consistency, the hypothesis must state that the original numbers are relative primes, precisely to bring the lemma in the restricted context.

As I said: pure formalism!