Saturday, June 18, 2005

Proof for n=4 using Gaussian Integers

In today's blog, I will show how it is possible to use Gaussian Integers to establish a proof for Fermat's Last Theorem n = 4. Previously, I showed two proofs for this result. I showed a standard proof based on Pythagorean Triples (see here). Also, I showed how it could be derived from Fermat's proof that a right triangle cannot have a square area (see here).

The proof for the case n = 4 using Gaussian Integer is both very strange and very interesting. The proof that I present is taken from Paul Ribenboem's book Fermat's Last Theorem for Amateurs.

Please note that I use Greek letters to represent Gaussian Integers and Latin letters to represent rational integers. This is really to emphasize that reasoning with Gaussian Integers requires different assumptions. For example, the Well Ordering Principle no longer applies and 2 is no longer a prime.

Theorem: x4 + y4 = z2 has no solution in Gaussian Integers where xyz ≠ 0.

(1) First, I will show that if there is a solution in rational integers, then the following is true:

There exists α, β, γ, ε, λ such that:
ε * λ4n * α4 + β4 = γ2 where n ≥ 2. [See here for proof.]

(2) Second, I will show that if (1) is true, then there is another set of values: ε1, α1, β1, γ1 such that:

ε1 * λ4(n-1) * α14 + β14 = γ12. [See here for proof.]

(3) But then, repeating step (2) again and again, we eventually get to values: αi, βi, εi, γi where

εi * λ4i4 + βi4 = γi2

(4) Which contradicts step (1) where n ≥ 2. So we reject that there is a solution to FLT for n=4.

QED

Friday, June 17, 2005

Bezout's Identity for Gaussian Integers

Today's blog continues my discussion of Gaussian Integers. If you are unfamiliar with the concept of unique factorization, start here. For the full discussion about Gaussian Integers, start here.

Bezout's Identity states that the greatest common denominator of any two integers can be expressed as a linear combination with two other integers. For example, because we know that gcd(2,3)=1, we also know that 1 = 2(-1) + 3(1). The proof for rational integers can be found here.

Bezout's Identity is one of three main ideas that are required in order to prove unique factorization. The other two ideas you need are a Division Algorithm, which I detailed in my last blog, and Euclid's Lemma, which I will discuss in a future blog.

Before discussing Bezout's Identity, we will need a lemma that shows that the notion of greatest common denominator applies to Gaussian Integers.

Using the Division Algorithm for Gaussian Integers and Euclid's method for greatest common denominators, we are set. The idea behind Euclid's Method is to do a continuous number of divisions.

Let's assume that we have a,b. First, we divide a by b and get a remainder which I will call r1. Then we divide b by r1 and we get a second remainder which I will call r2. We can keep repeating this until eventually we get a remainder which is 0. We know that this will happen because each remainder is guaranteed by the Division Algorithm to be smaller than the remainder before. After at most b iterations, we will reach a remainder of 0.

Euclid's Method tells us that the last ri value we use is the remainder. It is guaranteed to be at least 1. To make the idea behind this lemma as clear as possible, I will throw out one very simple lemma:

Lemma 1: d divides a, d divides b , a = b + c, then d divides c.

(1) d divides a → there exists A such that a = dA.
(2) d divides b → there exists B such that b = dB
(3) a = b + c → c = a - b = d(A - B)

QED

Lemma 2: For any two Gaussian Integers, it is possible to find the greatest common denominator.

(1) Let α, β be two Gaussian Integers.

(2) We know that there exists η11 such that:
α = η1β + δ1 and 0 ≤ δ1 which is less than β

(3) β = η2*δ1 + δ2

(4) And: δ1 = η3*δ2 + δ3

(5) We can keep repeating this until eventually we get:
δn-3 = ηn-1 * δn-2 + δn-1
δn-2 = ηn * δn-1 + δn
δn-1 = ηn+1* δn

(6) We know that we eventually get to this point since Norm(δi+1) is always less than the Norm(δi) by the Division Algorithm.

(7) Now, we know that δn divides δn-1 by Step #5. We also know that δn divides δn-2 and therefore, it also divides δn-3 and so on up to β and then α. In other words, it is a common divisor for α and β. [By Lemma 1]

(8) But we also know that if a certain value γ divides both α and β, then it will necessarily divide δ1 and that it will also necessarily divide δ2 and so on. [Again, by Lemma 1]

(9) In other words, we have proven that δn is the greatest common divisor.

QED

Corollary: All quadratic integers that are characterized by a Division Algorithm possess a greatest common denominator.

This is true since all the arguments above only assume a Division Algorithm.

QED

Here is the proof for Bezout's Identity:

Lemma 3: Let α, β be Gaussian Integers. Then there exist two other Gaussian Integers, let's say, ζ, η such that gcd(α,β) = ζα + ηβ

(1) Based on Lemma 2, we have the following:
δn-2 = ηn * δn-1 + δn

(2) This can be restated as:
δn = δn-2 - ηn * δn-1

(3) Now, if we let ζ = 1 and γ = -η we have:
δn = ζ * (δn-2) + γ * (δn-1)

(4) Let's define the following:
δ0 = β
δ-1 = α

With this definition, we can view each step as a continuum of different δi values all the way up.

(5) Now, if you look at equation (2), it shows that at each point, any δi can be restated in terms of smaller values of δi-1 and δi-2. So that:
δn = δn-2 - ηn * δn-1 =
δn-2 - ηn * (δn-3 - ηn-1 * δn-2) =
δn-2(1 + ηnn-1) + δn-3(-ηn)

(6) Setting ζ = 1 + ηn * ηn-1, γ = -ηn, we get:
δn = ζ * δn-2 + γ*δn-3

(7) Again, we can take (5) and move it up one using the same equation:
δn = ζ * (δn-4 - ηn-2 * δn-3) + γ * δn-3 =
= δn-3(-ζ *ηn-2 + γ) + δn-4(ζ)

(8) This shows that we can simplify the equation to a 1 smaller number which can be restated as a linear combination.

(9) Eventually, we get to:
δn = ζ * α + η * β

where ζ = some Gaussian Integer value and η = some Gaussian Integer value.

QED

But now, with the proof of Bezout's Identity, we can get Euclid's Lemma as a corollary.

Corollary 3.1: Euclid's Lemma: if π is a prime that divides α * β, then it divides α or it divides β


(1) Assume π doesn't divide α.

Please note: π is selected as the Greek character equivalent of p. I am not using π to represent 3.14....

(2) Then gcd(π,α) = 1. [By definition of gcd, #1]

(3) From Lemma 3, we know that there exists ζ, η such that:
1 = ζ * α + η * π.

(4) Multiplying both sides by β gives us:
β = ζ * α * β + η * π * β

(5) Since π divides α * β, we know that there exists γ such that:
α * β = π * γ

(6) So we have:
β = ζ * π * γ + η * π * β = π * (ζ * γ + η * β)

QED

Corollary 3.2: Euclid's Generalized Lemma: if π divides α1 * α2 * ... * αn, then π divides at least one of the elements in the product.


(1) Let β1 = α2 * ... * αn

(2) Then π divides α1 * β1 which means by Euclid's Lemma that π divides α1 or β1.

(3) If it divides α1, we are done.

(4) If it divides β1, then we set β2 = α3 * ... * αn and repeat the argument.

(5) Eventually, we hit some αi that is divisible by π.

QED

Corollary 3.3 These results apply to all quadratic integers characterized by a Division Algorithm

Again, none of these arguments are specific to Gaussian Integers. They are true of any quadratic integer that has a division algorithm.

QED

Thursday, June 16, 2005

Division Algorithm for Gaussian Integers

In my previous blog, I showed the details for a proof that Gaussian Integers have unique factorization. If any of the information that I present gets confusing, I suggest that readers start here where I explain about unique factorization, Gaussian Integers, the norm function, and the reason I am using Greek letters to represent Gaussian Integers.

In today's blog, I will show how using the norm function, it is possible to arrive at a Division Algorithm for Gaussian Integers.

The Division Algorithm for rational integers is based on the Well-Ordering Principle and can be found here. It states that whenever we divide one integer by another integer, we are left with a quotient and remainder that are both integers and which are both unique to the division and the remainder is guaranteed to be less than the divisor.

In the lemma below I used Greek letters for Gaussian Integers, Latin letters for rational integers, and Z[i] to represent the set of Gaussian Integers.

Lemma: Division Algorithm for Gaussian Integers

Given: α, γ ∈ Z[i]

Then: there exists ζ, δ such that: α = ζγ + δ and Norm(δ) is less than Norm(γ)

(1) There exists a,b,c,d such that:
α = a + bi
γ = c + di


(2) α / γ = (a + bi) / (c + di) = (a + bi)(c - di) / (c2 + d2) =
= (ac - adi + bci - bdi2)/(c2 + d2) =
=(ac + bd)/(c2 + d2) + i[(bc - ad)/(c2 + d2)]


(3) Let r = (ac + bd)/(c2 + d2).

(4) Let s = (bc - ad)/(c2 + d2)

(5) So, α / γ = r + si

(6) And we know that both r,s are rational. We do not know if they are integers.

(7) We know that there are m,n which are integers such that absolute(r - m) ≤ (1/2) and absolute(s - n) ≤ (1/2). [For proof of this see here]

(8) Let ζ = m + ni.

(9) Let δ = α - ζγ → α = ζγ + δ

(10) Norm(δ) = Norm(α - ζγ) =
= Norm(γ[(α/γ) - ζ] = Norm(α/γ - ζ) * Norm(γ) =
= Norm(r + si - [m + ni]) * Norm(γ) =
= Norm(r - m + si - ni) * Norm(γ) =
= Norm([r - m] + [s -n]i) * Norm(γ) =
= [(r - m)2 + (s - n)2] * Norm(γ) ≤ [ (1/2)2 + (1/2)2]*Norm(γ) =
= (1/2)*Norm(γ)
which is less than Norm(γ)

QED

Wednesday, June 15, 2005

Properties of Gaussian Integers

In my last blog, I spoke about relationship between Gaussian Integers and Fermat's Last Theorem. I went into some detail about norm function which provides a mapping from Gaussian Integers to standard integers. Anyone who is not familiar with Gaussian Integers or the norm function should start here. Anyone not familiar with the idea of unique factorization, should start here.

When we look at standard integers, officially called rational integers, we recognize that most of their properties are based on the Well Ordering Principle. This is the idea that for any given set of nonnegative integers, there is always one that is the smallest. If any one is interested in seeing the proofs related to the Well Ordering Principle and rational integers, you can check out here.

With Gaussian Integers, we are looking at a domain where the Well Ordering Principle does not apply. In the case of rational integers, it was clear that they can be thought to extend across a number line. Gaussian Integers, in contrast, extend across two number lines: a rational integer line and an i integer line.

For this reason, the previous proofs do not apply. We will need to come up with new proofs for the basic ideas. The basic idea of unique factorization is built from the following ideas:

(1) A Division Algorithm: What assumptions can we make about division? What assumptions can we make about quotients and remainders? See here for the algorithm with regard to rational integers. See here for the algorithm with regard to Gaussian Integers.

(2) Bezout's Identity: This is the idea that the greatest common denominator of any two integers can be represented as an equation based on two other integers. See here for the identity with regard to rational integers. See here for the proof of the identity with regard to Gaussian Integers.

(3) Euclid's Lemma: This is the idea that if a prime integer divides the product of two integers, then either it divides the first integer or it divides the second. See here for the proof of Euclid's Lemma regarding rational integers. See here for the proof with regard to Gaussian Integers.

Unique Factorization, it turns out, comes directly from Euclid's Lemma. As a convention, I will use Greek letters to represent Gaussian Integers and Latin letters to represent Rational Integers. So that: α = a + bi where α is a Gaussian Integer and a,b are rational integers.

There is one trick that we need to do in addition to using norms. We need to talk about the idea of associates.

Definition: Associates: Two numbers are associates if one is equal to the other multiplied by a unit.

The Gaussian Integers have four different units: i,-i,1,-1 (see Corollary 4.1, here). So, we can see that 4, -4, 4i, and -4i are all associates of each other. So, when we are talking about unique factorization of primes, we are considering prime associates to be the same prime. So, when we prove unique factorization, we are really proving a unique set of prime-associates.

Theorem: Gaussian Integers posess Unique Factorization.

(1) We know that all non-zero, non-units are either primes or composed of primes. [By the definition of primes]
(2) Let's assume that a given number is made of two different sets of primes.
(4) So α = β12*...*βr = γ12*...*γs
(5) Now each prime βi must necessarily match a prime in γj by Euclid's Generalized Lemma. [See here for the proof of Euclid's Generalized Lemma for Gaussian Integers]
(6) But we can make the same argument for all βi so there must be an equal prime or associate in the set of γj.
(7) But then, there cannot be any prime left over since if we divide all the βi, then we are left with a unit.
(8) So, we have proven that the set of primes is necessarily unique.

QED

Corollary: All Euclidean Integers posessess unique factorization.

(1) By definition, all Euclidean Integers are characterized by a Division Algorithm. [See here for review of Euclidean Integers]

(2) All Euclidean Integers are therefore also characterized by Euclid's Generalized Lemma. [See here for the proof.]

(3) With these two results, the same arguments above apply to all Euclidean Integers.

QED