Blog Archives

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 pqP 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 existsR 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 LemmaSince 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 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

Advertisements

CoPrime Numbers : x^n + y^n = z^n


This post is about the equation:
xn + yn= zn

I will show that given any three integers that satisfy this equation, either:

(a) all three of them are coprime with each other

or                                         

(b) it is possible to cancel out common components and derive three numbers that are coprime.

Two numbers are coprime if they do not share any common divisors.

Definition 1: Coprime

Two numbers x,y are said to be coprime if and only if divides x, d divides y -> d = 1

Two numbers x,y are said to not be coprime if and only if there exists a value d > 1such that divides x, d divides y

Now, here’s the proof that was promised:

Lemma: We can reduce any solution to xn + yn = zn to a form where x,y,z are coprime.

To prove this, we will need to prove two things:

(1) If a factor divides any two values of this equation, then the n-power of it divides the n-power of the third value.

(2) If an n-power of a factor divides the n-power of a value, then the factor divides the value itself.

Step 1: For xn + yn = zn, the n-power of any common factor of two divides the n-power of the third.

Case I: Let’s assume d divides x, d divides y

(1) There exists x’, y’ such that: x = d(x’), y = d(y’)
(2) zn = xn + yn = (dx’)n + (dy’)n
= dn(x’)n + dn(y’)n
= dn[(x’)n + (y’)n]

Case II: Let’s assume d divides z and d divides x or d divides y

(1) Let’s assume d divides x (the same argument will work for y)
(2) There exists x’, z’ such that: x = d(x’), z = d(z’)
(3) We now say yn = zn – xn
(4) We can now follow the same reasoning as above.

QED

Step 2: dn divides xn → d divides x

(1) Let c be the greatest common denominator (gcd) for d,x.
(2) Let D = d / c, X = x / c.
(3) Now the gcd of (X,D) = 1. [See here for the explanation]
(4) So, the gcd of (Xn,Dn) = 1.
(5) We know that there exists such that xn = k * dn [Since dn divides xn ]
(6) Applying (2), we get (cX)n = k*(cD)n
(7) Which gives us: cnXn = k * cnDn
(8) Dividing cn from each side gives: Xn = Dn*k
(9) Now it follows that gcd(Dn,k) = 1.

(a) Assume gcd(Dn,k) = a, a > 1
(b) Then, a divides Dn and Xn [From 8]
(c) But gcd(Dn,Xn) ≠ 1.
(d) But this contradicts (4)
(e) So, we reject our assumption.

(10) So, we can conclude that k is an n-power. [See blog on Infinite Descent for the proof]
(11) Which means that there exists u such that un = k.
(12) And we get Dn * un = Xn
(13) And (Du)n = Xn
(14) Implying that Du = X and multiplying by c that du=x.
(15) Which proves that divides x.

QED