Thursday, September 01, 2005

Fermat's Last Theorem: n = 5 : Overview

The proof for Fermat's Last Theorem: n=5 turns out to be more complicated and more difficult than any of the previous proofs. This is perhaps not too surprising since otherwise, Euler or Gauss would have most likely found the proof.

The final proof was the work of two very talented mathematicians: Adrien-Marie Legendre and Johann Peter Gustav Lejeune Dirichlet. The solution rested on the work done on the Binomial Theorem and Continued Fractions.

Since the purpose of this blog is to present a complete set of proofs, I will need to take a step back from Fermat's Last Theorem and review the developments of these two ideas. The Binomial Theorem was the result of three major mathematicians: Pierre de Fermat, Blaise Pascal, and Sir Isaac Newton. Major work on continued fractions was done by Joseph Louis Lagrange.

I will not attempt to do a complete survey of either of these very broad fields. Instead, I will review the lives of the mathematicians mentioned above and go through the proofs of the major results which are used later in the proof for n=5.

Tuesday, August 30, 2005

Sophie's Proof

Sophie's Proof is the proof discovered by Sophie Germain that later led to the proof of Fermat's Last Theorem for n =5. The proof is very important historically in that it represents a new approach to the problem. Rather than demonstrating that no solution exists, Sophie shows for certain values of n, n must divide x,y, or z.

After this proof, it became traditional to divide Fermat's Last Theorem into two parts:

Case I: None of the three values x,y,z is divisible by n.
Case II: n divides 1 of the three values x,y,z.

Here is Sophie Germain's Theorem:

Theorem: If xn + yn = zn and n is a prime ≥ 3 and 2n+1 is a prime, then n must divide xyz.

(1) We can assume that x,y,z are relatively prime to each other. [See here]

(2) So, let's assume that n doesn't divide xyz.

(3) Since n is odd, we can set z' to -z and get:
xn + yn + (z')n = 0.

(4) We can rewrite this to be [see here for details]
-xn = (y+z)(y(n-1) - y(n-2)z + ... - yz(n-2) + z(n-1))

(5) From this, we can show that:
y+z and y(n-1) - y(n-2)z + ... - yz(n-2) + z(n-1) are relatively prime since:

(a) Assume that they are not relatively prime.
(b) Then, there exists a prime p such that p divides y+z and p divides y(n-1) - y(n-2)z + ... - yz(n-2) + z(n-1).
(c) from this, we know that z ≡ -y (mod p).
(d) Using the fact that they are congruent (see here), we get:
y(n-1) - y(n-2)z + ... - yz(n-2) + z(n-1)
(n-1) - y(n-2)(-y) + ... -y(-y)(n-2) + (-y)(n-1)
y(n-1) + y(n-1) + ... + y(n-1) + y(n-1) ≡ (n)y(n-1)
(e) So from Euclid's Lemma, p either divides n or it divides y(n-1).
(f) But p doesn't divide n since:
(i) n is prime so p would equal n (a prime is only divisible by itself or 1)
(ii) And then n would divide (-x)n
(iii) Which means that it would divide x (from Euclid's Generalized Lemma)
(iv) But this impossible by step #2.
(g) And p doesn't divide y(n-1) because then p would divide y (Euclid's Generalized Lemma) and p would also divide z (since it divides y and it divides y+z), but this is impossible by step #1.
(h) So we have a contradiction and we reject our assumption.

(6) From Step #5 (see here), we can conclude that there exists a such that:
y + z = an

(7) But we can make this same argument for z+x and x + y where:
-yn = (x + z)(x(n-1) - x(n-2)z + ... -xz(n-2) + z(n-1))
-zn = (x + y)(x(n-1) - x(n-2)y + ... -xy(n-2) + y(n-1))

(8) So we know that there exists b,c where:
z + x = bn
x + y = cn

(9) We also know that any value un ≡ ±1 or 0 (mod 2n + 1) since:

(a) Assume that 2n+1 doesn't divide un [ we only need to consider the case where it is not congruent to 0]
(b) Since 2n+1 is a prime, we can apply Fermat's Little Theorem to get:
u2n ≡ 1 (mod 2n+1)
(c) And this means that:
(un)2 ≡ 1 (mod 2n + 1)
(d) So that un ≡ ± 1 (mod 2n+1) [See here for review of modular arithmetic]

(10) From this, we can conclude that (2n+1) divides xyz' since:

(a) Assume 2n+1 doesn't divide xyz'.
(b) Then, from step #9, we have:
xn ≡ ± 1
yn ≡ ± 1
zn ≡ ± 1
(c) But this is impossible since:
xn + yn + (-z)n ≡ 0 (mod 2n+1)
± 1 ± 1 ± 1 cannot be congruent to 0 (mod 2n+1)
(d) So, we reject(a).

(11) Let's assume that (2n+1) divides x. (We will be able to make the same type of argument if it divides y or z')

(12) Then 2x = bn + cn + (-a)n since from step #6 and step #8, we know that:
2x = z + x + x + y -y - z = bn + cn + (-a)n

(13) And we can conclude that (2n+1) divides acb since;

(a) We assumed that 2n+ 1 divides x. This gives us:
bn + cn + (-a)n ≡ 0 (mod 2n+1)

(b) Now, we can apply the same argument as Step #10 since:

(i) Assume that 2n+1 doesn't divide acb

(ii) From step #9 and (i) above, we can conclude that bn, cn, (-a)n ≡ ± 1.

(iii) But this is impossible since:
± 1 ± 1 ± 1 cannot be congruent to 0 (mod 2n+1)

(iv) So we can reject our assumption in (i) and conclude that 2n+1 divides acb.

(14) But (2n+1) can't divide abc since:

(a) (2n+1) can't divide b since:

(i) 2n+1 divides b → 2n+1 divides bn → 2n+1 divides z + x [since by step #8, z + x = bn.]
(ii) We know that 2n+1 divides x, so if it divides z+x, it must also divide z.
(iii) But this is impossible since x,z have no common factors by step #1.

(b) (2n+1) can't divide c for the same reason as above. That is, x,y have no common factors by step #1.

(c) (2n+1) can't divide a since:

(i) Assume (2n+1) divides a.
(ii) Then (2n+1) divides y + z which means that z ≡ -y (mod 2n+1)
(iii) We know from Step #5, there exists a value d, e such that:
dn = y(n-1) - y(n-2)z + ... - yz(n-2) + z(n-1).
en = x(n-1) - x(n-2)y + ... -xy(n-2) + y(n-1).

(iv) Applying (ii) gives us:
dn ≡ (n)y(n-1) (mod 2n+1) [See Step #5d]

(v) Since we know that x ≡ 0 (mod 2n + 1) [from Step #11], we get:
en ≡ (0)(n-1) - (0)(n--2)y + ... -(0)y(n-2) + y(n-1) ≡ y(n-1) (mod 2n+1)

(vi) Appyling (iv), this gives us:
dn ≡ (n)en (mod 2n+1)

(vii) From Step #9, we know that dn,en are 0,1, or -1. This means that they must both be equal to 0 since this is the only way that 0 ≡ n*0.

(viii) But if 2n+1 divides both dn,en, then it divides both d,e from Euclid's Lemma

(ix) But 2n+1 divides e implies that it also divides y (from (v).)

(x). But then it divides both x,y which goes against step #1.

(xi). So we have a contradiction and we reject (i).

(15) And this means that step #14 contradicts step #13 so we reject Step #2.


Corollary: x5 + y5 = z5 → 5 divides xyz.

This is true by above since 5 is a prime and 2*5+1 = 11 is a prime.



Fermat's Little Theorem

Despite its name, Fermat's Little Theorem is one of Pierre de Fermat's most important theorems. Fermat first presented it without proof in one of his letters in 1640. Leonhard Euler provided the first published proof in 1736. The theorem is very useful as a way of testing very large primes.

In a nutshell, the proof states that given an integer a and a prime p that does not divide a, then we know that a(p-1) has a remainder of 1 when divided by p.

From this theorem, then we know that:
472 ≡ 1 (mod 3).
1106 ≡ 1 (mod 7).

From the basic ideas of modulus (see here for review), we also know that:
(472)n ≡ 1 (mod 3)
(1106)n ≡ 1 (mod 7)

This theorem is also the foundation of Sophie's Proof (see here for the details), an important result from the mathematician Sophie Germain.

Theorem: If an integer a is not divisible by a prime p, then ap-1 ≡ 1 (mod p).

(1) From the Division Algorithm, we know that any number divided by an integer p has a remainder between 0 and p-1.

(2) This means that for any value a there is exactly p-1 possible congruences.
a ≡ 0 (mod p) or
a ≡ 1 (mod p) or
a ≡ p-1 (mod p)

(3) Consider the values 0a, 1a, 2a,... (p-1)a.

(4) It turns out that each of these values (0a, 2a, ...) is equal to a unique congruence when divided by p since:

(a) Assume that 2 of the values are equal to the same congruence: let's say ia, ja
(b) So ia ≡ ja (mod p)
(c) This tells us that p divides ia - ja (from the definition of )
(d) Which means that p divides a(i-j).
(e) From Euclid's Lemma, we know that p must divide i-j (since a is not divisible by p)
(f) But then i = j since both values are between 0 and p.

(5) So, this tells us that:
(1a)(2a)...(p-1)a ≡ (1)(2)...(p-1) (mod p). [Applying the principles of modular arithmetic]

(6) We also know that (1a)(2a)*...*(p-1)a = a(p-1)(p-1)! [See here for a review of factorials such as (p-1)!]

(7) Putting (5) and (6) together gives us:
a(p-1)(p-1)! ≡ (p-1)! (mod p).

(8) Since (p-1)! is not equal to 0, we can divide this from both sides of the modulus (see Lemma 4, here) and get:
a(p-1) ≡ 1 (mod p).