For those who are not familiar with Fermat's Last Theorem, you may wish to start here.
In Leonhard Euler's original proof for Fermat's Last Theorem n=3, he made a mistake. For anyone interested in seeing the details of the proof, it is perhaps comforting to know that a genius like Euler was capable of getting the details wrong. The details of this blog are based on Harold M. Edwards's book, Fermat's Last Theorem.
The mistake came when Euler tried to prove the key lemma of his proof. In his published proof, Euler attempted to prove this lemma using imaginary numbers. Euler is credited with the invention of the notation for imaginary numbers and one of the most fascinating equations ever derived which is known as Euler's Identity:
eiπ=-1
So, it is not too surprising that he would apply this method to Fermat's proof. It is also very interesting to note that a less innovative method can be constructed based on Euler's other work. This is what I did in the proof that I presented earlier.
Also interesting is the fact that this technique turns out to be a very important innovation which makes possible additional proofs for n=5, n=7, and Kummer's proof for regular primes.
Euler tries to prove the following lemma:
Lemma: Given that p2 + 3q2 is a cube, show that there exist a,b such that p = a3 - 9ab2 and q = 3a2b - 3b3.
Here's Euler's idea. What if we presuppose that there exists numbers of the form:
a + b√-3
If we allow that these numbers exist, then we have the following equation:
p2 + 3q2 = (p + q√-3)(p - q√-3)
So far so good. Mathematicals in general will allow any extension of numbers as long as the extension is logically consistent. The rational numbers extend the integers. Real numbers extend the rational numbers and Complex numbers extend the real numbers.
Euler proceeds to show that the two complex numbers (p + q√-3, p - q√-3) are relatively prime to each other. His proof here also works. I will add the details for this proof later.
He then concludes that the two complex numbers must, therefore, be cubes based on the reasoning of the Relatively Prime Divisor Lemma. This is the mistake!
In modern notation, Euler assumed that Z[√-3] was characterized by unique factorization. This is not completely correct. In actual fact, Z[(-1 + √-3)/2] is characterized by unique factorization. I go into more detail on this subject in my blog about Euclidean integers. If you are not familiar with quadratic integers, start here.
This result would be greatly extended by Carl Friedrich Gauss.
The purpose of this blog is to present the story behind Fermat's Last Theorem and Wiles' proof in a way accessible to the mathematical amateur.
Saturday, June 04, 2005
Friday, June 03, 2005
Fermat's Last Theorem: n = 3 : last lemma needed for proof
It may surprising that we only need one more lemma to finish Euler's proof for Fermat's Last Theorem: n=3. This is an easy one. For those interested in seeing the entire proof for Fermat's Last Theorem: n = 3, start here.
Lemma: For all odd numbers, there exists a value n such that the number is equal to 4n ± 1 with n greater than 0.
(1) Let S = the set of all odd numbers representable by 4n + 1 or 4n - 1
(2) We know that 1 is an element of this set since 1 = 4(0) + 1
(3) We can then presuppose that there is some value v such that all odd numbers less than or equal to v are describeable by 4n + 1 or 4n - 1. We know that v is greater or equal to 1
(4) Now, we will prove that if v is of the form 4n + 1 or 4n - 1, then v + 2 is also of this form.
Case I: v is of the form 4n + 1
v + 2 = 4n + 1 + 2 = 4n + 3 = 4(n+1) - 1
Case II: v is of the form 4n - 1
v + 2 = 4n - 1 + 2= 4n + 1
(5) By the Principle of Mathematical Induction, we have proven this lemma.
QED
Lemma: For all odd numbers, there exists a value n such that the number is equal to 4n ± 1 with n greater than 0.
(1) Let S = the set of all odd numbers representable by 4n + 1 or 4n - 1
(2) We know that 1 is an element of this set since 1 = 4(0) + 1
(3) We can then presuppose that there is some value v such that all odd numbers less than or equal to v are describeable by 4n + 1 or 4n - 1. We know that v is greater or equal to 1
(4) Now, we will prove that if v is of the form 4n + 1 or 4n - 1, then v + 2 is also of this form.
Case I: v is of the form 4n + 1
v + 2 = 4n + 1 + 2 = 4n + 3 = 4(n+1) - 1
Case II: v is of the form 4n - 1
v + 2 = 4n - 1 + 2= 4n + 1
(5) By the Principle of Mathematical Induction, we have proven this lemma.
QED
Thursday, June 02, 2005
Fermat's Last Theorem: n = 3 : multiplication with a2 + 3b2
Today's blog is a bit shorter than the previous ones. It shows the relationship which was probably the original reason why Pierre de Fermat was interested in this equation.
This is part of the larger proof for Fermat's Last Theorem: n=3 which was first published by Leonhard Euler.
Lemma: Multiplying two polynomials of the form a2 + 3b2 results in a polynomial with the same form.
(a2 + 3b2)(c2 + 3d2) = a2 (c2 + 3d2) + 3b2 (c2 + 3d2) =
= a2c2 + 3a2d2 + 3b2c2 +9b2d2 =
= a2c2 - 6abcd + 9b2d2 + 3a2d2 + 6abcd + 3b2c2 =
= (ac - 3bd)2 + 3(ad + bc)2
QED
This is part of the larger proof for Fermat's Last Theorem: n=3 which was first published by Leonhard Euler.
Lemma: Multiplying two polynomials of the form a2 + 3b2 results in a polynomial with the same form.
(a2 + 3b2)(c2 + 3d2) = a2 (c2 + 3d2) + 3b2 (c2 + 3d2) =
= a2c2 + 3a2d2 + 3b2c2 +9b2d2 =
= a2c2 - 6abcd + 9b2d2 + 3a2d2 + 6abcd + 3b2c2 =
= (ac - 3bd)2 + 3(ad + bc)2
QED
Wednesday, June 01, 2005
Fermat's Last Theorem: n = 3: Division of a2 + 3b2 by 2
In today's blog, I will go over the case of where a2 + 3b2 is an even number. This result is part of the proof of Fermat's Last Theorem for n=3. If you would like to see the full proof, start here.
Lemma: if 2 divides a polynomial of form a2 + 3b2, then 4 also divides the polynomial and this division by 4 results in another polynomial of the same form.
In other words, we will prove two propositions:
(1) We know that a,b have the same parity (they are both odd or they are both even). Otherwise, a2 + 3b2 would not be divisible by 2
(2) If they are both even, then it is easy to show that 4 divides a2 + 3b2 and that the result is of the same form:
(3) So, we can assume that they are both odd.
(4) Now, there exists m,n such that a = 4m ± 1, b = 4n ± 1 [See here for proof]
(5) From this, we know that 4 divides either a + b or a - b
(6) I will now show that in both cases, the lemma is proven.
Case I: 4 divides a + b
Case II: 4 divides a - b
QED
Lemma: if 2 divides a polynomial of form a2 + 3b2, then 4 also divides the polynomial and this division by 4 results in another polynomial of the same form.
In other words, we will prove two propositions:
- if 2 divides a2 + 3b2, then 4 also divides it.
- if 4 divides a2 + 3b2, then there exists c,d such that a2 + 3b2 = 4*(c2 + 3d2)
(1) We know that a,b have the same parity (they are both odd or they are both even). Otherwise, a2 + 3b2 would not be divisible by 2
(2) If they are both even, then it is easy to show that 4 divides a2 + 3b2 and that the result is of the same form:
(a) There exists c,d such that a = 2c and b = 2d
(b) a2 + 3b2 = (2c)2 + 3(2d)2 = 4(c2 + 3d2)
(3) So, we can assume that they are both odd.
(4) Now, there exists m,n such that a = 4m ± 1, b = 4n ± 1 [See here for proof]
(5) From this, we know that 4 divides either a + b or a - b
(6) I will now show that in both cases, the lemma is proven.
Case I: 4 divides a + b
(a) First, 4(a2 + 3b2) = (12 + 3*12)(a2 + 3b2) = (a - 3b)2 + 3(a + b)2 [See here for proof]
(b) Since a - 3b = (a + b) - 4b, we know that 4 divides a - 3b
(c) So, this gives us that 42 divides (a - 3b)2 + 3(a + b)2 which also means that:
4 divides a2 + 3b2 [Since 42 divides (a - 3b)2 + 3(a+b)2 implies 42 divides 4(a2 + 3b2)]
(d) Since 4 divides a - 3b and a + b, we know that there exists u,v such that: u = (a - 3b)/4 and v = (a + b)/4
(e) 4(u2 + 3v2) = 4{[(1/4)(a - 3b)]2 + 3[(1/4)(a + b)]2} =
= (1/4)(a2 + 9b2 + 3a2 + 3b2) =
= (1/4)(4a2 + 12b2) = a2 + 3b2
Case II: 4 divides a - b
(a) The argument here is the same as for case I except that we set 4(a2 + 3b2) = (12 + 3*(-1)2)(a2 + 3b2) = (a + 3b)2 + 3(a - b)2 [See here for proof.]
(b) Then after proving that 42 divides this result, we let u = (1/4)(a + 3b) and let v = (1/4)(a - b).
(c) Then 4(u2 + 3v2) = a2 + 3b2
QED
Tuesday, May 31, 2005
Fermat's Last Theorem: n = 3 : Division with a2 + 3b2
In today's blog, I will show that if you divide a polyonomial of form a2 + 3b2 with a prime of this same form, then you end up a polynomial that still has the same form.
This result is needed for the proof of Fermat's Last Theorem for n=3 that was first presented by Leonhard Euler. For those interested in seeing the entire proof, please start here.
Lemma: if a prime of form p2 + 3q2 divides a2 + 3b2, then there exists c,d such that:
a2 + 3b2 = (p2 + 3q2)(c2 + 3d2)
(1) There exists f such that a2 + 3b2 = (p2 + 3q2)f.
(2) (pb - aq)(pb + aq) = p2b2 - a2q2 + (3q2b2 - 3q2b2) =
= p2b2 + 3q2b2 - 3q2b2 - a2q2 =
= b2 ( p2 + 3q2 ) - q2 ( a2 + 3b2 )
(3) Now the prime p2 + 3q2 divides either pb - aq or pb + aq since:
(pb - aq)(pb+aq) = (p2 + 3q2)(b2 - q2f) [From Euclid's Lemma and steps (1), (2)]
(4) So that there exists a value F such that:
(p2 + 3q2)F equals either pb + aq or pb - aq
(5) Now, from multiplication of polynomials with this form, we know that:
(p2 + 3(±q)2)(a2 + 3b2) = (pa ± 3qb)2 + 3(pb ± aq)2
(6) So, p2 + 3q2 divides pa ± 3qb since:
(pa ± 3qb)2 = (p2 + 3q2)(a2 + 3b2) - 3(pb ± aq)2 =
(p2 + 3q2)[(a2 + 3b2) - 3(F)2]
(7) So, there exists c,d such that:
pa ± 3qb = c(p2 + 3q2)
pb ± aq = d(p2 + 3q2)
(8) Which means that:
(pa ± 3qb)2 + 3(pb ± aq)2 =
(c * (p2 + 3q2))2 + 3[d * (p2 + 3q2)]2
(9) Putting it altogether means that:
(a2 + 3b2) divided by (p2 + 3q2) =
(pa ± 3qb)2 + 3(pb ± aq)2 divided by (p2 + 3q2)2 [From step (5)]
= [c * (p2 + 3q2)]2 + 3[d * (p2 + 3q2)]2 divided by (p2 + 3q2)2 =
c2 + 3d2
QED
This result is needed for the proof of Fermat's Last Theorem for n=3 that was first presented by Leonhard Euler. For those interested in seeing the entire proof, please start here.
Lemma: if a prime of form p2 + 3q2 divides a2 + 3b2, then there exists c,d such that:
a2 + 3b2 = (p2 + 3q2)(c2 + 3d2)
(1) There exists f such that a2 + 3b2 = (p2 + 3q2)f.
(2) (pb - aq)(pb + aq) = p2b2 - a2q2 + (3q2b2 - 3q2b2) =
= p2b2 + 3q2b2 - 3q2b2 - a2q2 =
= b2 ( p2 + 3q2 ) - q2 ( a2 + 3b2 )
(3) Now the prime p2 + 3q2 divides either pb - aq or pb + aq since:
(pb - aq)(pb+aq) = (p2 + 3q2)(b2 - q2f) [From Euclid's Lemma and steps (1), (2)]
(4) So that there exists a value F such that:
(p2 + 3q2)F equals either pb + aq or pb - aq
(5) Now, from multiplication of polynomials with this form, we know that:
(p2 + 3(±q)2)(a2 + 3b2) = (pa ± 3qb)2 + 3(pb ± aq)2
(6) So, p2 + 3q2 divides pa ± 3qb since:
(pa ± 3qb)2 = (p2 + 3q2)(a2 + 3b2) - 3(pb ± aq)2 =
(p2 + 3q2)[(a2 + 3b2) - 3(F)2]
(7) So, there exists c,d such that:
pa ± 3qb = c(p2 + 3q2)
pb ± aq = d(p2 + 3q2)
(8) Which means that:
(pa ± 3qb)2 + 3(pb ± aq)2 =
(c * (p2 + 3q2))2 + 3[d * (p2 + 3q2)]2
(9) Putting it altogether means that:
(a2 + 3b2) divided by (p2 + 3q2) =
(pa ± 3qb)2 + 3(pb ± aq)2 divided by (p2 + 3q2)2 [From step (5)]
= [c * (p2 + 3q2)]2 + 3[d * (p2 + 3q2)]2 divided by (p2 + 3q2)2 =
c2 + 3d2
QED
Monday, May 30, 2005
Fermat's Last Theorem: n = 3: More a2 + 3b2
Today's blog presents another lemma associated with the polynomial a2 + 3b2. This lemma is used in the proof for Fermat's Last Theorem: n=3 that was first presented by Leonhard Euler. It is believed that Pierre de Fermat knew this proof but it took the work of a genius like Euler to recreate it. You can see the full proof for Fermat's Last Theorem n=3 by starting here.
Lemma: if a2 + 3b2 has an odd factor that is not of this form, then the quotient has an odd factor which is not of this form.
In other words, given the following:
(1) So there exists f,g such that fg = a2 + 3b2, f is odd and f is not in the form p2 + 3q2
(2) Let's assume that all of the odd factors of g have the form p2 + 3q2
(3) Now g = a series of primes p1 * p2 * ... * pn [By the Fundamental Theoreom of Arithmetic]
(4) In this series, we can replace all instances of 2 with instances of 4.
(5) Now we can divide all instances of 4 from g and from a2 + 3b2 and still have a result in the form of p2 + 3q2. [See here for proof]
(6) Likewise, we can divide all odd primes from g since we are assuming that all odd factors take the form p2 + 3q2. [The proof is found here.]
(7) But then this leaves f = p2 + 3q2 which is a contradiction.
(8) Therefore, we reject our assumption.
QED
Lemma: if a2 + 3b2 has an odd factor that is not of this form, then the quotient has an odd factor which is not of this form.
In other words, given the following:
- There exists f which is a factor of a value a2 + 3b2
- f does not have the form p2 + 3q2
- A value F such that fF = a2 + 3b2
- A value f' such that f' divides F and such that it does not have the form p2 + 3q2
(1) So there exists f,g such that fg = a2 + 3b2, f is odd and f is not in the form p2 + 3q2
(2) Let's assume that all of the odd factors of g have the form p2 + 3q2
(3) Now g = a series of primes p1 * p2 * ... * pn [By the Fundamental Theoreom of Arithmetic]
(4) In this series, we can replace all instances of 2 with instances of 4.
(a) We know that if 2 divides a2 + 3b2, then 4 divides it. [See here for proof]
(b) We know that f is odd so each instance of 4 necessarily divides g
(5) Now we can divide all instances of 4 from g and from a2 + 3b2 and still have a result in the form of p2 + 3q2. [See here for proof]
(6) Likewise, we can divide all odd primes from g since we are assuming that all odd factors take the form p2 + 3q2. [The proof is found here.]
(7) But then this leaves f = p2 + 3q2 which is a contradiction.
(8) Therefore, we reject our assumption.
QED
Sunday, May 29, 2005
Fermat's Last Theorem: n = 3: a2 + 3b2
The essence of Euler's proof for Fermat's Last Theorem, n = 3, is realizing the properties of values that can be represented by the formula: a2 + 3b2.
In today's blog, I will present a lemma that illustrates one of the surprising properties of the above formula.
This blog will continue the details of the proof that was begun in a previous blog.
Lemma: If gcd(a,b)=1, then every odd factor of a2 + 3b2 has this same form.
In other words, for every odd factor of a2 + 3b2, there exists c,d such that the odd factor = c2 +3d2
(1) Let x be a positive, odd factor of a2 + 3b2
(2) Then, there exists a value f such that:
a2 + 3b2 = xf
(3) We can assume that x is greater than 1 (since if x = 1 it's only factor is itself and 1 = 12 + 3(0)2.)
(4) There exists integers m,n such that:
a = mx ± c
b = nx ± d
where c,d can be positive or negative.
(5) Now, we can assume that c,d have absolute values that are less than (1/2)x.
(a) From the Division Algorithm (see Theorem 1, here), we know that c is less than x.
(b) Assume that c ≥ (1/2)x
(c) c' = x - c = -(c - x)
(d) a = mx + c = (m+1)x + c - x = (m+1)x - (x - c) = (m+1)x - c'
(e) abs(c') is less than (1/2)x since c' = x - c
(6) From step #4, we have:
a2 + 3b2 =
(mx ± c)2 + 3(nx ± d)2 =
m2x2 ± 2mxc + c2 + 3n2x2 ± 6nxd + 3d2 =
= x(m2x ± 2mc + 3n2x ± 6nd) + c2 + 3d2
(7) So x divides c2 + 3d2 since from step #1, since x is a factor of a2 + 3b2.
(8) So, there exists y such that:
c2 + 3d2 = xy
(9) Now from step #5 above, we have:
xy = c2 + 3d2 is less than [(1/2)x]2 + 3[(1/2)x]2 = (1/4)x2 + (3/4)x2 = x2.
(10) Now, we can conclude that y is less than x from:
(a) Since c2, d2 are nonnegative, it follows that xy is nonnegative.
(b) From step #9, xy is less than x2
(c) Since x is positive, the only way that this can be true is if y is less than x.
(11) We also know that c2 + 3d2 ≠ 0 because:
(a) Assume c2 + 3d2 = 0.
(b) Then c=0, d=0 since c2 and 3d2 are both nonnegative.
(c) But then: a = mx, b = nx and x divides both a,b.
(d) Which contradicts gcd(a,b)=1 so we reject our assumption.
(12) Let g = gcd(c,d). We know there exists C,D such that c = gC, d=gD, gcd(C,D)=1. [From the properties of greatest common denominators]
(13) Now we also know that g2 divides y because:
(a) xy =c2 +3d2 = (gC)2 + 3(gD)2 = g2(C2 + 3D2)
(b) Assume there is a prime p that divides g but doesn't divide y.
(c) Then p divides g and p divides x
(d) Then, there exists X,G where x = Xp, g = Gp
(e) And, p divides a and b since
a = mx + c = mpX + GpC = p(mX + GC)
b = nx + d = npX + GpD = p(nX + GD)
(f) But this is impossible since a,b are coprime.
(g) So, there is no prime p which divides g but does not divide y.
(h) Which proves that g divide y and further that g2 divides y
(14) Since g2 divides y, there exists z such that:
y = g2z
(15) Now, it follows that there exist C,D such that:
xz = C2 + 3D2 where gcd(C,D)=1
(a) xy = g2(C2 + 3D2) [from step #13a above]
(b) gcd(C,D) = 1 [from step #12 above]
(c) Then substituting z from step #14 gives us:
xz = C2 + 3D2
(16) Now we have enough to conclude that x is of the form p2 + 3q2
(a) Assume that x is not of this form.
(b) From step #15, we have xz = C2 + 3D2 where gcd(C,D)=1.
(c) Then there must exist w such that w divides z and w is not of the form p2 + 3q2 [See here
for the proof of this lemma]
(d) Now, w ≠ 1 since 1 = 12 + 3(0)2
(e) So, w is smaller than z [since w is greater than 1 and w divides z]
(f) But then w is less than x [since z is less than y (step #14, since y = g2z) and y is less than x (step #10)]
(g) But now, we have proven that the existence of x proves the existence of a smaller factor w which divides a smaller value of the same form.
QED
In today's blog, I will present a lemma that illustrates one of the surprising properties of the above formula.
This blog will continue the details of the proof that was begun in a previous blog.
Lemma: If gcd(a,b)=1, then every odd factor of a2 + 3b2 has this same form.
In other words, for every odd factor of a2 + 3b2, there exists c,d such that the odd factor = c2 +3d2
(1) Let x be a positive, odd factor of a2 + 3b2
(2) Then, there exists a value f such that:
a2 + 3b2 = xf
(3) We can assume that x is greater than 1 (since if x = 1 it's only factor is itself and 1 = 12 + 3(0)2.)
(4) There exists integers m,n such that:
a = mx ± c
b = nx ± d
where c,d can be positive or negative.
(5) Now, we can assume that c,d have absolute values that are less than (1/2)x.
(a) From the Division Algorithm (see Theorem 1, here), we know that c is less than x.
(b) Assume that c ≥ (1/2)x
(c) c' = x - c = -(c - x)
(d) a = mx + c = (m+1)x + c - x = (m+1)x - (x - c) = (m+1)x - c'
(e) abs(c') is less than (1/2)x since c' = x - c
(6) From step #4, we have:
a2 + 3b2 =
(mx ± c)2 + 3(nx ± d)2 =
m2x2 ± 2mxc + c2 + 3n2x2 ± 6nxd + 3d2 =
= x(m2x ± 2mc + 3n2x ± 6nd) + c2 + 3d2
(7) So x divides c2 + 3d2 since from step #1, since x is a factor of a2 + 3b2.
(8) So, there exists y such that:
c2 + 3d2 = xy
(9) Now from step #5 above, we have:
xy = c2 + 3d2 is less than [(1/2)x]2 + 3[(1/2)x]2 = (1/4)x2 + (3/4)x2 = x2.
(10) Now, we can conclude that y is less than x from:
(a) Since c2, d2 are nonnegative, it follows that xy is nonnegative.
(b) From step #9, xy is less than x2
(c) Since x is positive, the only way that this can be true is if y is less than x.
(11) We also know that c2 + 3d2 ≠ 0 because:
(a) Assume c2 + 3d2 = 0.
(b) Then c=0, d=0 since c2 and 3d2 are both nonnegative.
(c) But then: a = mx, b = nx and x divides both a,b.
(d) Which contradicts gcd(a,b)=1 so we reject our assumption.
(12) Let g = gcd(c,d). We know there exists C,D such that c = gC, d=gD, gcd(C,D)=1. [From the properties of greatest common denominators]
(13) Now we also know that g2 divides y because:
(a) xy =c2 +3d2 = (gC)2 + 3(gD)2 = g2(C2 + 3D2)
(b) Assume there is a prime p that divides g but doesn't divide y.
(c) Then p divides g and p divides x
(d) Then, there exists X,G where x = Xp, g = Gp
(e) And, p divides a and b since
a = mx + c = mpX + GpC = p(mX + GC)
b = nx + d = npX + GpD = p(nX + GD)
(f) But this is impossible since a,b are coprime.
(g) So, there is no prime p which divides g but does not divide y.
(h) Which proves that g divide y and further that g2 divides y
(14) Since g2 divides y, there exists z such that:
y = g2z
(15) Now, it follows that there exist C,D such that:
xz = C2 + 3D2 where gcd(C,D)=1
(a) xy = g2(C2 + 3D2) [from step #13a above]
(b) gcd(C,D) = 1 [from step #12 above]
(c) Then substituting z from step #14 gives us:
xz = C2 + 3D2
(16) Now we have enough to conclude that x is of the form p2 + 3q2
(a) Assume that x is not of this form.
(b) From step #15, we have xz = C2 + 3D2 where gcd(C,D)=1.
(c) Then there must exist w such that w divides z and w is not of the form p2 + 3q2 [See here
for the proof of this lemma]
(d) Now, w ≠ 1 since 1 = 12 + 3(0)2
(e) So, w is smaller than z [since w is greater than 1 and w divides z]
(f) But then w is less than x [since z is less than y (step #14, since y = g2z) and y is less than x (step #10)]
(g) But now, we have proven that the existence of x proves the existence of a smaller factor w which divides a smaller value of the same form.
(h) We can use the same argument to presuppose a value w' which is smaller than w and another value w'' which is smaller than w'. In other words, we have a contradiction by the method of infinite descent.
QED