Euclidean Coprime Integers: xn + yn = zn

In a previous blog, I showed that given rational integers x,y,z such that:
xⁿ + yⁿ = zⁿ

We can assume that x,y,z are relatively prime. See here for the details.

It turns out that we can make the same statement about all Euclidean Integers. For those not familiar with Euclidean Integers, please review here.

Lemma 1: For Euclidean Integers, relatively prime divisors of n-powers are themselves n-powers.

This theorem says that if gcd(v,w) = 1 and vw = zⁿ
Then, there exists x,y such that v = xⁿ, w = yⁿ

(1) So, we start with gcd(v,w) = 1, vw = zⁿ
(2) Assume that v is not equal to any number xⁿ
(3) v ≠ 1 since 1 is an xⁿ power
(4) Now, v is divisible by a prime number p. [Fundamental Theorem of Arithmetic for Euclidean Integers]
(5) So, there exists k such that v = pk
(6) p divides z since zⁿ = vw = pkw [By applying Euclid's Lemma for Euclidean Integers]
(7) So, there exists m such that z=pm
(8) So, zⁿ = vw = pkw = (pm)ⁿ = pⁿmⁿ
(9) Dividing p from both sides gives us:
kw = p^(n-1)mⁿ
(10) From Euclid's Lemma, p divides k or w.
(11) It can't divide w since it already divides v and gcd(v,w)=1. Therefore, it divides k
(12) We can apply this same argument for each p in p^(n-1)
(13) So, we can conclude that p^(n-1) divides k.
(14) So, there exists V such that k = p^(n-1)*V
(15) So, kw = p^(n-1)mⁿ = p^(n-1)*V*w
(16) Dividing p^(n-1) from both sides gives us:
vW = mⁿ
(17) Now, gcd(V,w)=1 since V is a divisor of v and gcd(v,w) = 1
(18) Likewise, V cannot be an n-power. If it were, then v = pⁿV would make v an n-power which goes against our assumption.
(19) Finally, V is less than v since p^(n-1) > 1.
(20) Thus, we have a contradiction by infinite descent.

QED

Lemma 2: Given xⁿ + yⁿ = zⁿ and x,y,z are Euclidean Integers, we can assume that x,y,z are relatively prime.

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 xⁿ + yⁿ = zⁿ, 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) zⁿ = xⁿ + yⁿ = (dx')ⁿ + (dy')ⁿ
= dⁿ(x')ⁿ + dⁿ(y')ⁿ
= dⁿ[(x')ⁿ + (y')ⁿ]

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 yⁿ = zⁿ - xⁿ
(4) We can now follow the same reasoning as above.

QED

Step 2: dⁿ divides xⁿ → 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 proof.]
(4) So, the gcd of (Xⁿ,Dⁿ) = 1.
(5) We know that there exists k such that xⁿ = k * dⁿ [Since dⁿ divides xⁿ ]
(6) Applying (2), we get (cX)ⁿ = k*(cD)ⁿ
(7) Which gives us: cⁿXⁿ = k * cⁿDⁿ
(8) Dividing cⁿ from each side gives: Xⁿ = Dⁿ*k
(9) Now it follows that gcd(Dⁿ,k) = 1.

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

(10) So, we can conclude that k is an n-power. [By the lemma above]
(11) Which means that there exists u such that uⁿ = k.
(12) And we get Dⁿ * uⁿ = Zⁿ
(13) And (Du)ⁿ = Zⁿ
(14) Implying that Du = Z and multiplying by c that du=z.
(15) Which proves that d divides z.

QED

Euclid's Method for the Greatest Common Denominator

The greatest common denominator (gcd) is the largest common factor shared by two or more positive integers. In the case of 4,2 the greatest common denominator is 2. Since all integers are divisible by 1, the greatest common denominator of any two integers is guaranteed to be at least 1. If the gcd of two integers is 1, those integers are said to be relatively prime or coprime. In other words, they do not have any common divisors.

It is perhaps obvious on the face there exists a gcd for any two integers and there exists a method for finding this value. Here is the proof. The method for finding the greatest common denominator is found in Euclid's Elements and is therefore known today as Euclid's algorithm. Here is a link to Euclid's proof in the Elements.

But what about quadratic integers? What about Gaussian Integers or Eisenstein Integers? (for those not familiar with quadratic integers, refer to here).

It turns out that if there is a division algorithm available, then for any two integers, there is necessarily a greatest common denominator. In other words, we can prove that Euclid's method for finding the gcd applies. Here is the proof (note: in the example referenced, it refers to Gaussian Integers, but the same proof applies to Eisenstein Integers and other types of quadratic integers that are characterized by a division algorithm).

For this reason, all quadratic integers that are characterized by a division algorithm are said to be Euclidean.

One result of this is that for any two Euclidean integers (quadratic integers that have a division algorithm) that are not relatively prime, it is possible to derive two smaller integers which are relatively prime.

Lemma: gcd(x,y)=d is greater than 1 → there exists X,Y such that x = Xd, y = Yd and gcd(X,Y)=1.

(1) Assume that gcd(X,Y) = D which is greater than 1.
(2) Then D divides X,Y such that there exists X = DX', Y=DY'
(3) And x = DX'd, y = DY'd
(4) So that Dd divides both x and y.
(5) But Dd > d which is impossible since d is the greatest common divisor.
(6) So we reject (1).

QED

Corollary: This result holds for all quadratic integers that are Euclidean.

This is true since the result only depends on the gcd which we showed above holds for all Euclidean Integers.

QED

Lemma: gcd(x,y)=1 → gcd(xⁿ,yⁿ)=1.

(1) Assume that gcd(xⁿ,yⁿ) = d which is greater than 1.
(2) Since d is greater than 1, there must exist a prime p that divides d. [See here for the proof of Fundamental Theorem of Arithmetic]
(3) if p divides xⁿ, then p divides x. [See here for the proof of Euclid's Generalized Lemma]
(4) For the same reason, p would also divide y.
(5) But this is a contradiction since gcd(x,y)=1.
(6) So we reject (1).

QED

Corollary: This holds true for all Euclidean Integers

This proof depends on a proof for unique factorization and Euclid's Generalized Lemma.

(1) Euclid's Generalized Lemma holds true for all Euclidean Integers. [See here for proof].
(2) Unique Factorization holds true for all Euclidean Integers. [See here for proof].

QED