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.
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
Saturday, May 28, 2005
Fermat's Last Theorem: n= 3: Key Lemma
One of the surprising discoveries in the Fermat's Last Theorem n=3 is how much more complicated it is than n=4. In this blog, I will present a seemingly obscure lemma that is very important in Euler's proof for n=3. The full proof for n=3 can be found at this link.
In my opinion, this obscure lemma is the most beautiful part of the proof. It is surprisingly elegant.
Here is the lemma:
Lemma: Given that there exist p,q with the following properties:
(a) gcd(p,q)=1 (gcd = greatest common denominator)
(b) p,q have opposite parities (one is odd, one is even)
(c) p2 + 3q2 is a cube
Then there exists a,b such that:
(a) p = a3 - 9ab2
(b) q = 3a2b - 3b3
(c) gcd(a,b)=1
(d) a,b have opposite parities
Proof:
(1) Let u3 = p2 + 3q2. [Since we know that p2 + 3q2 is a cube.]
(2) We know that u is odd since p,q have opposite parities [that is, one is odd, one is even].
(3) We know then that u must be of the form a2 + 3b2. [Since any odd factor would also have to have the same form, see here for the lemma regarding odd factors of p2 + 3q2]
(4) Now, (a2 + 3b2)3 = (a2 + 3b2)[(a2 - 3b2)2 + 3(2ab)2]
(5) And, (a2 + 3b2)[(a2 - 3b2)2 + 3(2ab)2] =
[ a(a2 - 3b2) - 3b(2ab)]2 + 3[a(2ab)+b(a2-3b2)]2 [See here for the proof.]
(6) And: [ a(a2 - 3b2) - 3b(2ab)]2 + 3[a(2ab)+b(a2-3b2)]2 =
= [a3 - 3ab2 - 6ab2]2 + 3(2a2b + a2b - 3b3)2 =
=[a3 -9ab2]2 + 3(3a2b - 3b3)2.
(7) Which combined with step (1) gives us:
p2 + 3q2 = [a3 -9ab2]2 + 3(3a2b - 3b3)2
(8) Which means that we could define a,b such that:
p = a3 -9ab2.
q = 3a2b - 3b3.
gcd(a,b)=1 [since otherwise, any common factor would divide p and q].
(9) We also know that a,b have opposite parities since:
(a) If a,b are both odd, then, p is even since p = odd - odd and q is even since q = odd - odd which is impossible since p,q have opposite parities.
(b) If a,b are both even, then p is even since p = even - even and q is even since q = even - even which is impossible.
QED
In my opinion, this obscure lemma is the most beautiful part of the proof. It is surprisingly elegant.
Here is the lemma:
Lemma: Given that there exist p,q with the following properties:
(a) gcd(p,q)=1 (gcd = greatest common denominator)
(b) p,q have opposite parities (one is odd, one is even)
(c) p2 + 3q2 is a cube
Then there exists a,b such that:
(a) p = a3 - 9ab2
(b) q = 3a2b - 3b3
(c) gcd(a,b)=1
(d) a,b have opposite parities
Proof:
(1) Let u3 = p2 + 3q2. [Since we know that p2 + 3q2 is a cube.]
(2) We know that u is odd since p,q have opposite parities [that is, one is odd, one is even].
(3) We know then that u must be of the form a2 + 3b2. [Since any odd factor would also have to have the same form, see here for the lemma regarding odd factors of p2 + 3q2]
(4) Now, (a2 + 3b2)3 = (a2 + 3b2)[(a2 - 3b2)2 + 3(2ab)2]
since (a2 + 3b2)2 = a4 + 6a2b2 + 9b4 =
= a4 + 12a2b2 - 6a2b2 + 9b4 =
(a2 - 3b2)2 + 3(2ab)2
(5) And, (a2 + 3b2)[(a2 - 3b2)2 + 3(2ab)2] =
[ a(a2 - 3b2) - 3b(2ab)]2 + 3[a(2ab)+b(a2-3b2)]2 [See here for the proof.]
(6) And: [ a(a2 - 3b2) - 3b(2ab)]2 + 3[a(2ab)+b(a2-3b2)]2 =
= [a3 - 3ab2 - 6ab2]2 + 3(2a2b + a2b - 3b3)2 =
=[a3 -9ab2]2 + 3(3a2b - 3b3)2.
(7) Which combined with step (1) gives us:
p2 + 3q2 = [a3 -9ab2]2 + 3(3a2b - 3b3)2
(8) Which means that we could define a,b such that:
p = a3 -9ab2.
q = 3a2b - 3b3.
gcd(a,b)=1 [since otherwise, any common factor would divide p and q].
(9) We also know that a,b have opposite parities since:
(a) If a,b are both odd, then, p is even since p = odd - odd and q is even since q = odd - odd which is impossible since p,q have opposite parities.
(b) If a,b are both even, then p is even since p = even - even and q is even since q = even - even which is impossible.
QED
Friday, May 27, 2005
Fermat's Last Theorem: n = 3: Step 4
Today's blog continues the proof for Fermat's Last Theorem n=3 which was started in a previous blog.
Lemma: Given the following conditions:
(a) x,y,z is a solution to x3 + y3 = z3
(b) two values of x,y,z are derived from p+q,p-q
(c) p,q coprime
(d) p,q opposite parity
(e) p,q positive
(f) 2p*(p2 + 3q2) is a cube.
(g) gcd(2p,p2 + 3q2) = 3
Then:
There exists a smaller solution A,B,C such that A3 + B3 = C3.
(1) First, we note that 3 divides p but not q. Since 3 divides 2p [see #g] and p,q are coprime [see #c].
(2) So, there exists s such that:
p = 3s and
2p * (p2 + 3q2) = 2p*(3s*3s + 3q2) = 2*3s*(3*3s2 + 3q2) =
= 32*2s(3s2 + q2)
(3) Now 32*2s, 3s2 + q2 are relatively prime since:
(4) So, 32*2s, 3s2 + q2 are cubes [By Relatively Prime Divisor Lemma] since 32*2s(3s2 + q2) = 2p * (p2 + 3q2) [see #2] and 2p * (p2 + 3q2) is a cube [see #f in given].
(5) Then, there exists a,b such that:
q = a3 - 9ab2
s = 3a2b - 3b3
gcd(a,b)=1
since:
gcd(q,s)=1 [See #3e above]
q,s have opposite parities [see #3c above]
q2 + 3s2 is a cube [see #4 above]
[See here for the lemma that establishes this]
(6) From, this we can show that 2b, a-b, a+b are cubes
A3 = 2b
B3 = a - b
C3 = a + b
(8) Which means that there is another solutions to Fermat's Last Theorem n=3 since:
A3 = 2b = a + b - (a - b) = C3 - B3
(9) Now, since:
C3 = a + b which is less than s = (3b)(a - b)(a + b) which is less than p = 3s which is less than either x3 or z3 since either z3 = (2p)*(p2 + 3q2) or x3 = (2p) * (p2 + 3q2).
(10) So, a solution here leads necessarily to a smaller solution of FLT n=3.
QED
Lemma: Given the following conditions:
(a) x,y,z is a solution to x3 + y3 = z3
(b) two values of x,y,z are derived from p+q,p-q
(c) p,q coprime
(d) p,q opposite parity
(e) p,q positive
(f) 2p*(p2 + 3q2) is a cube.
(g) gcd(2p,p2 + 3q2) = 3
Then:
There exists a smaller solution A,B,C such that A3 + B3 = C3.
(1) First, we note that 3 divides p but not q. Since 3 divides 2p [see #g] and p,q are coprime [see #c].
(2) So, there exists s such that:
p = 3s and
2p * (p2 + 3q2) = 2p*(3s*3s + 3q2) = 2*3s*(3*3s2 + 3q2) =
= 32*2s(3s2 + q2)
(3) Now 32*2s, 3s2 + q2 are relatively prime since:
(a) 3 doesn't divide q [step #1]
(b) so 3 doesn't divide 3s2 + q2
(c) Since p=3s [#2], s is the same parity as p which means that s,q have opposite parity [see #d in given].
(d) But if s,q have opposite parity, then 2 doesn't divide 3s2 + q2 since it must be odd.
(e) Finally, gcd(s,q)=1 since gcd(p,q)=1. [see #c in the given]
(4) So, 32*2s, 3s2 + q2 are cubes [By Relatively Prime Divisor Lemma] since 32*2s(3s2 + q2) = 2p * (p2 + 3q2) [see #2] and 2p * (p2 + 3q2) is a cube [see #f in given].
(5) Then, there exists a,b such that:
q = a3 - 9ab2
s = 3a2b - 3b3
gcd(a,b)=1
since:
gcd(q,s)=1 [See #3e above]
q,s have opposite parities [see #3c above]
q2 + 3s2 is a cube [see #4 above]
[See here for the lemma that establishes this]
(6) From, this we can show that 2b, a-b, a+b are cubes
(a) a,b have different parity since q,s have different parity [see #3c above] since:(7) But this means there exists A,B,C such that:
Case I: a,b are both even
q = a3 - 9ab2 = even - even = even.
s = 3a2b - 3b3 = even - even = even
which is impossible since q,s have different parity.
Case II: a,b are both odd
q = a3 - 9ab2 = odd - odd = even
s = 3a2b - 3b3 = odd - odd = even.
which is impossible since q,s have different parity.
(b) a + b, a - b are odd since a,b have different parity so 2 is coprime.
(c) b is coprime to a + b and a - b, otherwise, it would divide a which goes against gcd(a,b)=1
(d) a + b, a - b are coprime since any common factor would be odd and divide both a and b since 2a = a + b + a - b and 2b = a + b - (a - b)
(e) 32*2s is a cube [see #4 above] so 32*2s =32*2[3a2b - 3b3] = 33*2[a2b - b3] = 33(2b)(a+b)(a - b) is a cube.
(f) But if 33(2b)(a+b)(a - b) is a cube, then (2b)(a+b)(a - b) is a cube.
(g) But if (2b)(a+b)(a - b) is a cube and gcd(2b,a+b,a-b)=1 [by #6b,#6c,#6d], then by the Relatively Prime Divisor Lemma, 2b, a+b, and a-b are all cubes.
A3 = 2b
B3 = a - b
C3 = a + b
(8) Which means that there is another solutions to Fermat's Last Theorem n=3 since:
A3 = 2b = a + b - (a - b) = C3 - B3
(9) Now, since:
C3 = a + b which is less than s = (3b)(a - b)(a + b) which is less than p = 3s which is less than either x3 or z3 since either z3 = (2p)*(p2 + 3q2) or x3 = (2p) * (p2 + 3q2).
(10) So, a solution here leads necessarily to a smaller solution of FLT n=3.
QED
Thursday, May 26, 2005
Fermat's Last Theorem: n = 3: Step 3
Today's blog continues the proof for Fermat's Last Theorem n=3 that I began in a previous blog.
With this step, we enter the heart of the proof for Fermat's Last Theorem n=3. This step is a bit complicated so I will only be able to provide an outline at this point. Later on, I will update this blog and insert all the details.
Lemma: Given the following conditions:
(a) x,y,z is a solution to x3 + y3 = z3
(b) two values of x,y,z are derived from p+q,p-q
(c) p,q coprime
(d) p,q opposite parity
(e) p,q positive
(f) 2p*(p2 + 3q2) is a cube.
(g) gcd(2p,p2 + 3q2) = 1
Then:
There exists a smaller solution A,B,C such that A3 = B3 + C3.
(1) 2p and p2 + 3q2 are cubes. [From Relatively Prime Divisors Lemma]
(2) First, we show that there exists two values a,b such that: [See here for the lemma.]
p = a3 - 9ab2, q = 3a2b - 3b3, gcd(a,b)=1, a,b opposite parity
(3) This gives us that:
2p =2a3 - 18ab2 =(2a)(a - 3b)(a + 3b)
(4) 2a, a - 3b,a + 3b are all coprime.
(5) So, once again, all three are cubes. [By Relatively Prime Divisors Lemma] so that we have A,B,C such that:
2a = A3
a - 3b = B3
a + 3b = C3
(6) But this gives us another solution to Fermat's Last Theorem: n=3 since:
A3 = 2a = a - 3b + a + 3b = B3 + C3
(7) Now, this solution is necessarily smaller than x,y,z since:
(A3)(B3)(C3) = (2a)(a - 3b)(a + 3b) = 2p
And from our previous work, either:
x3 = (2p)*(p2 + 3q2) or
z3 = (2p)*(p2 + 3q2)
QED
With this step, we enter the heart of the proof for Fermat's Last Theorem n=3. This step is a bit complicated so I will only be able to provide an outline at this point. Later on, I will update this blog and insert all the details.
Lemma: Given the following conditions:
(a) x,y,z is a solution to x3 + y3 = z3
(b) two values of x,y,z are derived from p+q,p-q
(c) p,q coprime
(d) p,q opposite parity
(e) p,q positive
(f) 2p*(p2 + 3q2) is a cube.
(g) gcd(2p,p2 + 3q2) = 1
Then:
There exists a smaller solution A,B,C such that A3 = B3 + C3.
(1) 2p and p2 + 3q2 are cubes. [From Relatively Prime Divisors Lemma]
(2) First, we show that there exists two values a,b such that: [See here for the lemma.]
p = a3 - 9ab2, q = 3a2b - 3b3, gcd(a,b)=1, a,b opposite parity
(3) This gives us that:
2p =2a3 - 18ab2 =(2a)(a - 3b)(a + 3b)
(4) 2a, a - 3b,a + 3b are all coprime.
(a) First, 2a is coprime with a - 3b and a + 3b. Both a - 3b and a + 3b are odd since a,b have opposite parity. If a had a common factor with either, then this factor would also divide b which goes against our assumption.
(b) If any odd prime greater than 3 divides a - 3b and a + 3b, then it must divide a since 2a = a - 3b + a + 3b and it must divide b since 6b
= a + 3b - (a - 3b). But this is impossible.
(c) We already showed that 2 can't divide a - 3b, a + 3b. So all we need to prove is that 3 also can't divide both. If 3 divides both then it divides a since 2a = a - 3b + a + 3b, then it also divides p since p = a3 - 9ab2. But it can't divide p since gcd(2p,p2 + 3q2)=1. So, 3 can't divide both.
(5) So, once again, all three are cubes. [By Relatively Prime Divisors Lemma] so that we have A,B,C such that:
2a = A3
a - 3b = B3
a + 3b = C3
(6) But this gives us another solution to Fermat's Last Theorem: n=3 since:
A3 = 2a = a - 3b + a + 3b = B3 + C3
(7) Now, this solution is necessarily smaller than x,y,z since:
(A3)(B3)(C3) = (2a)(a - 3b)(a + 3b) = 2p
And from our previous work, either:
x3 = (2p)*(p2 + 3q2) or
z3 = (2p)*(p2 + 3q2)
QED
Wednesday, May 25, 2005
Fermat's Last Theorem: n = 3: Step 2
Today's blog continues the proof that I started earlier. The full proof for Fermat's Last Theorem: n = 3 can be found in my previous blog.
Today, I will show the proof for this lemma:
Lemma: if p,q are coprime, p,q opposite parity, then gcd(2p,p2 + 3q2) = 1 or 3
(1) Assume that there is a prime f which divides both 2p and p2 + 3q2.
(2) We know that it can't be 2 since p2 + 3q2 is odd since p,q have opposite parity.
(3) Let's assume that f is greater than 3. So that there exist P,Q such that:
2p = fP, p2 + 3q2 = Qf
(4) Now, f isn't 2 so we know that 2 must divide P so there exists a value H that is half of P and:
p = fH
(5) So combining the two equations, we get:
3q2 = Qf - p2 = Qf - f2H2 = f(Q - fH2)
(6) f doesn't divide 3 since it is greater than 3. So by Euclid's Lemma, it must divide q.
(7) But this contradicts p,q being coprime since it also divides p so we reject our assumption.
QED
Today, I will show the proof for this lemma:
Lemma: if p,q are coprime, p,q opposite parity, then gcd(2p,p2 + 3q2) = 1 or 3
(1) Assume that there is a prime f which divides both 2p and p2 + 3q2.
(2) We know that it can't be 2 since p2 + 3q2 is odd since p,q have opposite parity.
(3) Let's assume that f is greater than 3. So that there exist P,Q such that:
2p = fP, p2 + 3q2 = Qf
(4) Now, f isn't 2 so we know that 2 must divide P so there exists a value H that is half of P and:
p = fH
(5) So combining the two equations, we get:
3q2 = Qf - p2 = Qf - f2H2 = f(Q - fH2)
(6) f doesn't divide 3 since it is greater than 3. So by Euclid's Lemma, it must divide q.
(7) But this contradicts p,q being coprime since it also divides p so we reject our assumption.
QED
Tuesday, May 24, 2005
Fermat's Last Theorem: n = 3: Step 1
This blog will explain the proof for the first step in Fermat's Last Theorem: n = 3. For the full proof, please start here. The details for this proof come from Leonhard Euler who was the first to make progress on Fermat's Last Theorem.
The first step will be stated as a lemma:
Lemma: x3 + y3 = z3 has a solution only if there exists p,q such that:
(a) gcd(p,q)=1
(b) p,q are positive
(c) p,q have opposite parity (that is, one is even, one is odd)
(d) 2p*(p2 + 3q2) is a cube.
(1) We can assume that x,y,z are coprime.
(2) Since, x,y,z are coprime, we know that at most one of them is even.
(3) We also know that at least one of them is even since if x and y are odd, then z must be even.
(4) So, we now divide this proof up into Case I: z is even and Case II: x is even. Since x,y are symmetrical, Case II will also cover the case where y is even.
Case I: z is even
(1) Then x,y are odd.
(2) x + y and x - y are even.
(3) Let 2p = x + y and 2q = x - y
(4) Then:
x = (1/2)[x + y + ( x - y )] = p + q
y = (1/2)[x + y - ( x - y )] = p - q
(5) Now gcd(p,q) = 1
(6) We can assume that p,q are positive
(7) p,q have to have different parities since x,y are both odd.
(8) Finally, 2p*(p2 + 3q2) is a cube.
z3 = x3 + y3 =
= (x + y)(x2 - xy + y2) =
= (p + q + p - q)[(p+q)2 - (p+q)(p-q) + (p-q)2] =
= 2p(p2 + 3q2)
Case II: x is even
(1) Then z,y are odd since they are coprime to x.
(2) z+y, z-y are both even.
(3) There exists p,q such that 2p = (z - y), 2q = (z + y)
(4) And z = (1/2)[(z - y) + (z + y)] = (1/2)(2p + 2q) = p + q, y = (1/2)[(z + y) - (z - y)] = (1/2)(2q - 2p) = q-p
(5) p,q have opposite parity since z,y are odd.
(6) gcd(p,q)= 1 [Same argument as Case I]
(7) p,q are positive [Same argument as Case I]
(8) 2p*(p2 + 3q2) is a cube.
x3 = z3 - y3 =
= (z - y)(z2 + zy + y2) =
= [q + p - (q - p)][(q+p)2 + (q+p)(q-p) + (q-p)2] =
= 2p*(p2 + 3q2)
QED
The first step will be stated as a lemma:
Lemma: x3 + y3 = z3 has a solution only if there exists p,q such that:
(a) gcd(p,q)=1
(b) p,q are positive
(c) p,q have opposite parity (that is, one is even, one is odd)
(d) 2p*(p2 + 3q2) is a cube.
(1) We can assume that x,y,z are coprime.
(2) Since, x,y,z are coprime, we know that at most one of them is even.
(3) We also know that at least one of them is even since if x and y are odd, then z must be even.
(4) So, we now divide this proof up into Case I: z is even and Case II: x is even. Since x,y are symmetrical, Case II will also cover the case where y is even.
Case I: z is even
(1) Then x,y are odd.
(2) x + y and x - y are even.
(3) Let 2p = x + y and 2q = x - y
(4) Then:
x = (1/2)[x + y + ( x - y )] = p + q
y = (1/2)[x + y - ( x - y )] = p - q
(5) Now gcd(p,q) = 1
(a) Assume f = gcd(p,q) is greater than 1
(b) Then there exists P,Q such that p = fP, q = fQ
(c) But then f divides both x,y since x = f(P + Q), y = f(P - Q)
(d) This is a contradiction since x,y are coprime.
(6) We can assume that p,q are positive
(a) From before p = (1/2)(x + y), q = (1/2)(x - y)
(b) x cannot equal y since they are coprime.
(c) if x + y is negative, then substitute (-x),(-y) since x3 + y3 = z3 implies that (-x)3 + (-y)3 = (-z)3
(d) if y is greater than x then flip x,y since they are symmetric.
(e) This covers all cases.
(7) p,q have to have different parities since x,y are both odd.
(8) Finally, 2p*(p2 + 3q2) is a cube.
z3 = x3 + y3 =
= (x + y)(x2 - xy + y2) =
= (p + q + p - q)[(p+q)2 - (p+q)(p-q) + (p-q)2] =
= 2p(p2 + 3q2)
Case II: x is even
(1) Then z,y are odd since they are coprime to x.
(2) z+y, z-y are both even.
(3) There exists p,q such that 2p = (z - y), 2q = (z + y)
(4) And z = (1/2)[(z - y) + (z + y)] = (1/2)(2p + 2q) = p + q, y = (1/2)[(z + y) - (z - y)] = (1/2)(2q - 2p) = q-p
(5) p,q have opposite parity since z,y are odd.
(6) gcd(p,q)= 1 [Same argument as Case I]
(7) p,q are positive [Same argument as Case I]
(8) 2p*(p2 + 3q2) is a cube.
x3 = z3 - y3 =
= (z - y)(z2 + zy + y2) =
= [q + p - (q - p)][(q+p)2 + (q+p)(q-p) + (q-p)2] =
= 2p*(p2 + 3q2)
QED
Sunday, May 22, 2005
Fermat's Last Theorem: Proof for n=3
Leonhard Euler came up with two proofs for Fermat's Last Theorem: n = 3.
One proof involved a very innovative method using irrational numbers. Unfortunately, Euler made a mistake in his proof. Despite this, his method revealed a very promising approach to Fermat's Last Theorem which was later taken up by Gauss, Dirichlet , and Kummer. I discuss the details of this method and Euler's mistake in another blog.
The other proof is less generalizable but still brilliant. This is the proof that I will present in today's blog.
The details of this proof are based largely on the work by H. M. Edwards in his book: Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.
Theorem: Euler's Proof for FLT: n = 3
x3 + y3 = z3 has integer solutions -> xyz = 0
(1) Let's assume that we have solutions x,y,z to the above equation.
(2) We can assume that x,y,z are coprime. [See here for the proof]
(3) First, we observe that there must exist p,q such that (see here for proof):
(4) Second, we know that gcd(2p,p2+3q2) is either 1 or 3. (see here for proof).
(5) If gcd(2p,p2+3q2)=1, then there must be a smaller solution to Fermat's Last Theorem n=3. (see here for proof).
(6) Likewise, if gcd(2p,p2+3q2)=3, then there must be a smaller solution to Fermat's Last Theorem n=3. (see here for proof).
(7) But then there is necessarily a smaller solution and we could use the same argument on this smaller solution to show the existence of an even smaller solution. We have thus shown a condition of infinite descent.
QED
One proof involved a very innovative method using irrational numbers. Unfortunately, Euler made a mistake in his proof. Despite this, his method revealed a very promising approach to Fermat's Last Theorem which was later taken up by Gauss, Dirichlet , and Kummer. I discuss the details of this method and Euler's mistake in another blog.
The other proof is less generalizable but still brilliant. This is the proof that I will present in today's blog.
The details of this proof are based largely on the work by H. M. Edwards in his book: Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.
Theorem: Euler's Proof for FLT: n = 3
x3 + y3 = z3 has integer solutions -> xyz = 0
(1) Let's assume that we have solutions x,y,z to the above equation.
(2) We can assume that x,y,z are coprime. [See here for the proof]
(3) First, we observe that there must exist p,q such that (see here for proof):
(a) gcd(p,q)=1
(b) p,q have opposite parities (one is odd; one is even)
(c) p,q are positive.
(d) 2p*(p2 + 3q2) is a cube.
(4) Second, we know that gcd(2p,p2+3q2) is either 1 or 3. (see here for proof).
(5) If gcd(2p,p2+3q2)=1, then there must be a smaller solution to Fermat's Last Theorem n=3. (see here for proof).
(6) Likewise, if gcd(2p,p2+3q2)=3, then there must be a smaller solution to Fermat's Last Theorem n=3. (see here for proof).
(7) But then there is necessarily a smaller solution and we could use the same argument on this smaller solution to show the existence of an even smaller solution. We have thus shown a condition of infinite descent.
QED
Thursday, May 19, 2005
Leonhard Euler
The next mathematician in the story of Fermat's Last Theorem is Leonhard Euler, whose name is pronounced "Oiler". Euler was one of the most prolific mathematicians of all time. One of those interests was number theory and he was the first mathematician to make progress on Fermat's famous problem (Fermat, himself, provided a proof for n=4). Euler was responsible for finding a proof for n=3 and for finding a method of proof using imaginary numbers. I will go into detail on both of these points in future blogs.Euler was born on April 15, 1707 in Basel Switzerland. His father was a Protestant minister with an interest in mathematics. In fact, his father attended lectures by the very famous Jakob Bernoulli. For those interested, the Bernoulli family is one of the most famous families in all the history of mathematics.
Euler entered the University of Basel when he was 14. He originally planned to study theology but his abilities in mathematics attracted the attention of Daniel and Nikolaus Bernoulli, sons of Jakob. The Bernoullis convinced Euler's father to let him study mathematics.
In 1727, he received second place in Grand Prize of the Paris Academy.
At 23, Euler became a professor of physics in St. Petersburg. In 1733, when he was 26, he married Katharina Gsell, the daughter of a Russian painter. They would have 13 children, only 5 of which survived infancy. Euler would later say that he made some of his greatest mathematical discoveries while he had a baby in his hands.
By 1740, he had lost the use of one of his eyes and was starting to lose sight in his other eye. By this time, he had a very strong reputation in mathematics. He had won the Grand Prize of the Paris Academy in 1738 and 1740.
In 1741, at the age of 34, he became Director of the Prussian Academy of Sciences in Berlin. He did not get along well with Frederick the Great and returned in 1766 to St. Petersburg where he stayed for the rest of his life. During this time, he wrote 380 articles, wrote books on the calculus of variations, the mathematics of planetary motions, on artillery and ballistics, on analysis, shipbuilding, and navigation among others. Frederick was apparently very upset when Euler left.
Euler's achievements are legendary. His total mathematical output fills over 70 large volumes. He was able to do all this even while he gradually lost his eyesight. For the last seventeen years of his life, he was completely blind. Almost half of all his output was accomplished during this time. He died in 1783 at the age of 76. Even after his death, it took 50 years to release his unpublished works.
It is really impossible to summarize Euler's achievements in the space of this blog. Instead, I will present just a glimpse of some of his very interesting results.
- Euler invented the notation ƒ(x) for function (1734), e for natural logs (1727), i as the square root of -1 (1777), the notation π for pi, the notation Σ for summation (1755), and the notation for finite diferences ∇y and ∇2 y.
- He was the first to apply Newton's calculus to physics.
- He showed the usefulness of using imaginary numbers as exponents. Which includes one of the most amazing results in mathematics, known as Euler's identity: eiπ=-1.
I go into detail about this equation here. It is used in the derivation of cyclotomic inteogers which are the basis for Ernst Kummer's proof for Fermat's Last Theorem.
- He solved many long standing mathematical problems including the Basel Problem, Fermat's Last Theorem for n=3, and many other of Fermat's unproved theorems and conjectures.
- He made many breakthroughs in physics deriving what are known today as Euler equations which are a set of laws of motion in fluid dynamics that are derived directly from Newton's laws of motions.
- Along wtih Daniel Bernoulli, he established the law of torque on a thin elastic beam.
In 1976, his image appeared on the Swiss 10 franc note.
The contents of this blog were based on two sources:
1. Wikipedia.com
2. MacTutor Biography of Euler
Tuesday, May 17, 2005
Fermat's Last Theorem: n = 4
The easiest proof for Fermat's Last Theorem is the case n = 4. The proof for n=3 is a bit tricker. What is nice about this proof is that it arises quite naturally from the solution to Pythagorean Triples but it also proves Fermat's Theorem for all values n > 2 where n is even if we can prove Fermat's Last Theorem for all values n > 2 where n is odd. In fact, we can use the same time of reasoning to prove for all values n > 2 where n is not a prime if we can prove it true for all values n > 2 where n is prime.
Many textbooks say Fermat himself published this proof. This is not completely true. Fermat published a proof showing that a right triangle cannot have its area equal to a square. Fermat's proof does by implication show that there is no solution to n=4 but it is a bit more complicated than the proof that I am about to show.
Theorem for FLT/n = 4: There are no integer solutions to:
x4 + y4 = z2 where xyz ≠ 0
(1) We can assume that x2,y2,z are coprime. [From here since (x2)2 + (y2)2 = z2]
(2) From the solution to Pythagorean Triples, we know that there exist p,q such that:
x2 = 2pq
y2 = p2 - q2
z = p2 + q2
(3) Now from this, we have another Pythagorean Triple since y2 + q2 = p2.
(4) So, there exist a,b such that:
q = 2ab
y = a2 - b2
p = a2 + b2
a,b are relatively prime.
(5) Combining equations, we have:
x2 = 2pq = 2(a2 + b2)(2ab) = 4(ab)(a2 + b2)
(6) Since ab and a2 + b2 are relatively prime, we know that they are both squares. [See here for the proof.]
(7) So, there exists P such that P2 = a2 + b2.
(8) But now we have reached infinite descent since:
P2 = a2 + b2 = p which is less than p2 + q2 = z which is less than z2.
NOTE: if xyz=0, then this argument does not hold. This proof only works for xyz ≠ 0.
(9) So, the existence of a solution to the initial equation leads necessarily to the existence of another smaller square that has the same properties.
QED
The case for n=4 is then stated as a corollary.
Corollary for FLT n = 4: There is no solution to:
x4 + y4 = z4 where xyz ≠ 0
Since this equation is equal to:
x4 + y4 = (z2)2
Corollary for FLT n divisible by 4: There is no solution to:
x4n' + y4n' = z4n' where xyz ≠ 0 and n' = (n/4)
Since this equation is equal to:
(xn')4 + (yn')4 = (z(2n'))2
Corollary for FLT n > 2: FLT is proven if FLT is proven for all cases where n is a prime.
The lesson learned from all this, is that we only need to proof that Fermat's Last Theorem is true for prime values of n.
If we prove that Fermat's Last Theorem is true for a given prime number, then it follows that it is true for any number which is divisible by that prime. For example, if we prove that there is no integer solution for x3 + y3 = z3, then we have likewise proven that there is no solution for (xi)3 + (yi)3 = (zi)3 = x3i + y3i = z3i.
This would also prove that x9 + y9 = z9 has no nontrivial integer solution.
Many textbooks say Fermat himself published this proof. This is not completely true. Fermat published a proof showing that a right triangle cannot have its area equal to a square. Fermat's proof does by implication show that there is no solution to n=4 but it is a bit more complicated than the proof that I am about to show.
Theorem for FLT/n = 4: There are no integer solutions to:
x4 + y4 = z2 where xyz ≠ 0
(1) We can assume that x2,y2,z are coprime. [From here since (x2)2 + (y2)2 = z2]
(2) From the solution to Pythagorean Triples, we know that there exist p,q such that:
x2 = 2pq
y2 = p2 - q2
z = p2 + q2
(3) Now from this, we have another Pythagorean Triple since y2 + q2 = p2.
(4) So, there exist a,b such that:
q = 2ab
y = a2 - b2
p = a2 + b2
a,b are relatively prime.
(5) Combining equations, we have:
x2 = 2pq = 2(a2 + b2)(2ab) = 4(ab)(a2 + b2)
(6) Since ab and a2 + b2 are relatively prime, we know that they are both squares. [See here for the proof.]
(7) So, there exists P such that P2 = a2 + b2.
(8) But now we have reached infinite descent since:
P2 = a2 + b2 = p which is less than p2 + q2 = z which is less than z2.
NOTE: if xyz=0, then this argument does not hold. This proof only works for xyz ≠ 0.
(9) So, the existence of a solution to the initial equation leads necessarily to the existence of another smaller square that has the same properties.
QED
The case for n=4 is then stated as a corollary.
Corollary for FLT n = 4: There is no solution to:
x4 + y4 = z4 where xyz ≠ 0
Since this equation is equal to:
x4 + y4 = (z2)2
Corollary for FLT n divisible by 4: There is no solution to:
x4n' + y4n' = z4n' where xyz ≠ 0 and n' = (n/4)
Since this equation is equal to:
(xn')4 + (yn')4 = (z(2n'))2
Corollary for FLT n > 2: FLT is proven if FLT is proven for all cases where n is a prime.
The lesson learned from all this, is that we only need to proof that Fermat's Last Theorem is true for prime values of n.
If we prove that Fermat's Last Theorem is true for a given prime number, then it follows that it is true for any number which is divisible by that prime. For example, if we prove that there is no integer solution for x3 + y3 = z3, then we have likewise proven that there is no solution for (xi)3 + (yi)3 = (zi)3 = x3i + y3i = z3i.
This would also prove that x9 + y9 = z9 has no nontrivial integer solution.
Thursday, May 12, 2005
Fermat's One Proof
In his life, Pierre de Fermat only left one proof in relation to number theory. He used his method of infinite descent to show that the area of a right triangle cannot be a square within the domain of whole numbers.
The proof itself was found after his death in his notes on Diophantus's Arithmetica.
In what follows, I will go through each sentence of Fermat's proof and provide details to make his step clear. My goal is to shed light on Fermat's thinking in his one existent proof.
I will show how this proof can also be used to prove the case of Fermat's Last Theorem where n = 4. In my next blog, I go over a simpler proof for n=4.
My analysis is based on the work by Harold M. Edwards called Fermat's Last Theorem. The translation is taken from T. L. Heath's translation.
Fermat writes:
(1) Fermat: "If the area of a right-angled triangle were a square, there would exist two biquadrates the difference of which would be a square number."
A biquadrate is a value to the fourth-power. So, the biquadrate of 2 is 24 = 16.
This corresponds to the following equation:
p4 - q4 = z2.
When I first read this, it was surprising to me that Fermat assumed that this equation was obvious from the problem of showing that right triangle's area cannot be equal to a square.
This equation proves n = 4 since if x4 + y4 = z4, then:
x4 = (x2)2 = z4 - y4
So, proving there is no right triangle that has an area equal to a square will also prove Fermat's Last Theorem for n=4.
The steps to this equation can be traced as follows:
(2) Fermat: "Consequently there would exist two square numbers the sum and difference of which would both be squares."
This one is a bit easier to derive
z2 = P4 - Q4 = (P2 + Q2)(P2 - Q2)
Now, all, we need to show is that (P2 + Q2) is relatively prime to (P2 - Q2) which means that p + q is realtively prime to p - q. [ The trick is to remember that p,q are relatively prime and they are of different parity (see 13(b) here). See here for details]
In other words, there exist two square numbers (P2,Q2) the sum (P2 + Q2) and difference (P2 - Q2) are both squares.
(3) Fermat: "Therefore we should have a square number which would be equal to the sum of a square and the double of another square..."
We know that P2 + Q2 is equal to a square. Let's say S2.
We also know that P2 - Q2 is equal to a square. Let's say T2
So that P2 = Q2 + T2
Which combined with the other equation gives us:
Q2 + T2 + Q2 = T2 + 2Q2 = S2
We can assume that S,P, Q are relatively prime and also that P,T,Q are relatively prime with S,P,T odd and Q even. [See here for details]
We can also assume that Q,S,T are relatively prime. [See here for details]
(4) Fermat: "...while the squares of which this sum is made up would themselves have a square number for their sum."
And as stated before: P2 = Q2 + T2.
(5) Fermat: "But if a square is made up of a square and the double of another square, its side, as I can very easily prove, is also similarly made up of a square and the double of another square."
So, he is saying this:
T2 + 2Q2 = S2 --> S = t2 + 2q2.
This means that
2Q2 = S2 - T2 = (S - T)(S + T)
And:
Q2 = (1/2)(S-T)(S+T)
Now Q,S,T are relatively prime. We know that Q, S-T, S+T are even. [see above for details]
Let S-T = 2u, S + T = 2v
So that Q2 = (1/2)(2u)(2v) = 2uv
Now, u,v are relatively prime [see here for details]
And, either u or v is even, let's assume u
So that, u = 2w and Q2 = 2(2w)v
And w,v are relatively prime so w,v are squares.
Let w = W2, v = V2
And S + T + S - T = 2S = 2u + 2v = 2(2W2 + V2)
So that S = 2W2 + V2
(6) Fermat: "From this we conclude that the said side is the sum of the sides about the right angle in a right-angled triangle and that the simple square contained in the sum is the base and the double of the other square is the perpendicular."
So, he is saying this:
S = 2W2 + V2 -> (2W2 )2 + ( V2)2 is a square.
(2W2 )2 + ( V2)2 = (2w)2 + ( v)2 = (u)2 + ( v)2 =
[(1/2)(S-T)]2 + [(1/2)(S+T)]2 =
[S2 - 2ST + T2]/4 + [S2 + 2ST + T2]/4 =
= [2S2 + 2T2]/4 = (S2 + T2)/2.
Now, since S2 = 2Q2 + T2
We have:
(2Q2 + T2 + T2)/2 = Q2 + T2
Which equals P2.
(7) Fermat: "This right-angled triangle will thus be formed from two squares, the sum and differences of which will be squares."
We can once again apply the Solution to the Pythagorean Triples so that:
2W2= 2mn
V2 = m2 - n2
P= m2 + n2
So we've proven that the difference is a square. Now, we need to prove that the sum is a square.
Since Q2 = 2(2w)v = 4W2V2.
Q2= 2(2mn)(m2 - n2)=4mn(m2 - n2).
And
(Q/2)2 = mn(m2 - n2)
Since m,n and m2 - n2 are relatively prime, then m,n,m2-n2 are all squares.
Letting m = M2 and n = N2
We get:
V2 = M4 - N4 = (M2 - N2)(M2 + N2)
Since M2 - N2, M2 + N2 are relatively prime, both the sum and differences are squares.
(8) Fermat: "But both these squares can be shown to be smaller than the squares originally assumed to be such that both their sum and differences are squares."
So M2 + N2 ≤ P2 + Q2.
Since M2 + N2 ≤ m + n is less than P which is less than P2 + Q2.
(9) Fermat: "Thus if there exist two squares such that their sum and differences are both squares, there will also exist two other integer squares which have the same property but a smaller sum"
We have proven that:
if P2 + Q2 is a square and P2 - Q2 is a square, then there exists M,N such that:
(a) M2+N2 is less than P2 + Q2
(b) M2 + N2 is a square
(c) M2 - N2 is a square.
(10) Fermat: "By the same reasoning we find a sum still smaller than the last found, and we can go on ad infinitum finding integer square numbers smaller and smaller which have the same property."
This leads to an infinite number of smaller solutions.
(11) Fermat: "This is, however, impossible because there cannot be an infinite series of numbers smaller than any given integer we please."
So that we have a proof by Infinite Descent.
(12) Fermat: "The margin is too small to enable me to give the proof completely and with all detail."
At least, this time we were able to reconstruct the proof. :-)
-Larry
The proof itself was found after his death in his notes on Diophantus's Arithmetica.
In what follows, I will go through each sentence of Fermat's proof and provide details to make his step clear. My goal is to shed light on Fermat's thinking in his one existent proof.
I will show how this proof can also be used to prove the case of Fermat's Last Theorem where n = 4. In my next blog, I go over a simpler proof for n=4.
My analysis is based on the work by Harold M. Edwards called Fermat's Last Theorem. The translation is taken from T. L. Heath's translation.
Fermat writes:
(1) Fermat: "If the area of a right-angled triangle were a square, there would exist two biquadrates the difference of which would be a square number."
A biquadrate is a value to the fourth-power. So, the biquadrate of 2 is 24 = 16.
This corresponds to the following equation:
p4 - q4 = z2.
When I first read this, it was surprising to me that Fermat assumed that this equation was obvious from the problem of showing that right triangle's area cannot be equal to a square.
This equation proves n = 4 since if x4 + y4 = z4, then:
x4 = (x2)2 = z4 - y4
So, proving there is no right triangle that has an area equal to a square will also prove Fermat's Last Theorem for n=4.
The steps to this equation can be traced as follows:
(a) A right triangle is characterized by the Pythagorean Theorem:
a2 + b2 = c2.
(b) The area of a rectangle is base x height.
(c) A right triangle of a given base and height is created by dividing the same rectangle across the diagonal.
(d) Therefore, the area of a right triangle is base * height / 2.
(e) Or, using a,b,c from above: area = ab/2
(f) From the solution to Pythagorean Triples, we know that:
a = (2pq)d
b = (p2 - q2)d
where we know that p,q are relatively prime.
(g)So, saying the area of a right triangle is equal to a square comes down to proving that there are no solutions for:
z2 = ((2pq)d[p2 - q2]d)/2 = (pq)(d2)[p2 - q2]
(h) From a previous result, we know that d will divide z so, we are left with showing no solutions for:
(z/d)2 = (pq)[p2 - q2]
(i) Since p,q are relatively prime, it follows that (pq) and [p2 - q2] are relatively prime [see here for details]
(j) From this we conclude, that pq is a square and p2 - q2 are squares.
(k) And since p,q are relatively prime, p,q are themselves squares.
(l) So, there exist P,Q such that p = P2 and q = Q2
(m) Since pq is a square, there exists a value k such that k2 = pq.
(n) And from (m), k divides (z/d), so we get:
(z/dk)2 = p2 - q2 = P4 - Q4
(2) Fermat: "Consequently there would exist two square numbers the sum and difference of which would both be squares."
This one is a bit easier to derive
z2 = P4 - Q4 = (P2 + Q2)(P2 - Q2)
Now, all, we need to show is that (P2 + Q2) is relatively prime to (P2 - Q2) which means that p + q is realtively prime to p - q. [ The trick is to remember that p,q are relatively prime and they are of different parity (see 13(b) here). See here for details]
In other words, there exist two square numbers (P2,Q2) the sum (P2 + Q2) and difference (P2 - Q2) are both squares.
(3) Fermat: "Therefore we should have a square number which would be equal to the sum of a square and the double of another square..."
We know that P2 + Q2 is equal to a square. Let's say S2.
We also know that P2 - Q2 is equal to a square. Let's say T2
So that P2 = Q2 + T2
Which combined with the other equation gives us:
Q2 + T2 + Q2 = T2 + 2Q2 = S2
We can assume that S,P, Q are relatively prime and also that P,T,Q are relatively prime with S,P,T odd and Q even. [See here for details]
We can also assume that Q,S,T are relatively prime. [See here for details]
(4) Fermat: "...while the squares of which this sum is made up would themselves have a square number for their sum."
And as stated before: P2 = Q2 + T2.
(5) Fermat: "But if a square is made up of a square and the double of another square, its side, as I can very easily prove, is also similarly made up of a square and the double of another square."
So, he is saying this:
T2 + 2Q2 = S2 --> S = t2 + 2q2.
This means that
2Q2 = S2 - T2 = (S - T)(S + T)
And:
Q2 = (1/2)(S-T)(S+T)
Now Q,S,T are relatively prime. We know that Q, S-T, S+T are even. [see above for details]
Let S-T = 2u, S + T = 2v
So that Q2 = (1/2)(2u)(2v) = 2uv
Now, u,v are relatively prime [see here for details]
And, either u or v is even, let's assume u
So that, u = 2w and Q2 = 2(2w)v
And w,v are relatively prime so w,v are squares.
Let w = W2, v = V2
And S + T + S - T = 2S = 2u + 2v = 2(2W2 + V2)
So that S = 2W2 + V2
(6) Fermat: "From this we conclude that the said side is the sum of the sides about the right angle in a right-angled triangle and that the simple square contained in the sum is the base and the double of the other square is the perpendicular."
So, he is saying this:
S = 2W2 + V2 -> (2W2 )2 + ( V2)2 is a square.
(2W2 )2 + ( V2)2 = (2w)2 + ( v)2 = (u)2 + ( v)2 =
[(1/2)(S-T)]2 + [(1/2)(S+T)]2 =
[S2 - 2ST + T2]/4 + [S2 + 2ST + T2]/4 =
= [2S2 + 2T2]/4 = (S2 + T2)/2.
Now, since S2 = 2Q2 + T2
We have:
(2Q2 + T2 + T2)/2 = Q2 + T2
Which equals P2.
(7) Fermat: "This right-angled triangle will thus be formed from two squares, the sum and differences of which will be squares."
We can once again apply the Solution to the Pythagorean Triples so that:
2W2= 2mn
V2 = m2 - n2
P= m2 + n2
So we've proven that the difference is a square. Now, we need to prove that the sum is a square.
Since Q2 = 2(2w)v = 4W2V2.
Q2= 2(2mn)(m2 - n2)=4mn(m2 - n2).
And
(Q/2)2 = mn(m2 - n2)
Since m,n and m2 - n2 are relatively prime, then m,n,m2-n2 are all squares.
Letting m = M2 and n = N2
We get:
V2 = M4 - N4 = (M2 - N2)(M2 + N2)
Since M2 - N2, M2 + N2 are relatively prime, both the sum and differences are squares.
(8) Fermat: "But both these squares can be shown to be smaller than the squares originally assumed to be such that both their sum and differences are squares."
So M2 + N2 ≤ P2 + Q2.
Since M2 + N2 ≤ m + n is less than P which is less than P2 + Q2.
(9) Fermat: "Thus if there exist two squares such that their sum and differences are both squares, there will also exist two other integer squares which have the same property but a smaller sum"
We have proven that:
if P2 + Q2 is a square and P2 - Q2 is a square, then there exists M,N such that:
(a) M2+N2 is less than P2 + Q2
(b) M2 + N2 is a square
(c) M2 - N2 is a square.
(10) Fermat: "By the same reasoning we find a sum still smaller than the last found, and we can go on ad infinitum finding integer square numbers smaller and smaller which have the same property."
This leads to an infinite number of smaller solutions.
(11) Fermat: "This is, however, impossible because there cannot be an infinite series of numbers smaller than any given integer we please."
So that we have a proof by Infinite Descent.
(12) Fermat: "The margin is too small to enable me to give the proof completely and with all detail."
At least, this time we were able to reconstruct the proof. :-)
-Larry
Monday, May 09, 2005
Infinite Descent
Pierre de Fermat was very proud of his technique known as Infinite Descent. He wrote that this method "will lead to marvelous advancement in the theory of numbers" (quoted from: http://fermat.workjoke.com/flt2.htm)
As he often did, Fermat left very few details on how to apply the method. He did provide one example of this method in his proof that the area of a right triangle cannot be equal to a square number. An elegant application of this proof is found in the case of FLT: n=4 where the proof rests on the method of infinite descent and the solution to Pythagorean Triples.
The basic method is very straight forward. One proves that if an assumption is true, it means that the assumption must also be true for an element that is smaller. In other words, an assumption leads to the proposition of an infinite number of cases where it is true.
This technique is especially useful in the domain of positive integers. In this case, infinite descent is impossible since it contradicts the Well Ordering Principle. In other words, there must always be a smallest element in any set of positive integers. But if there is a smallest element, then, there cannot be an infinite descent. In this way, the method can be used as way to prove by contradiction certain negative assumptions. It can also be used to prove a positive conclusion as I will show below.
Fermat is known to have used this technique to prove that there is no square equal to a right triangle. He left a proof using this technique for the case of n = 4 which I will go over in a future blog. He also wrote about its use in the proof for the case of n = 3 in a letter to Christian Huygens.
If Fermat had really found a proof for his theorem, it was without doubt based on this method.
To show the technique in action, I will use it to prove the following theorem:
Thereom: Relatively Prime Divisors of an n-power are themselves n-powers.
This theorem says that if gcd(v,w) = 1 and vw = zn
Then, there exists x,y such that v = xn, w = yn
(1) So, we start with gcd(v,w) = 1, vw = zn
(2) Assume that v is not equal to any number xn
(3) v ≠ 1 since 1 is an xn power
(4) Now, v is divisible by a prime number p. [Fundamental Theorem of Arithmetic]
(5) So, there exists k such that v = pk
(6) p divides z since zn = vw = pkw [By applying Euclid's Lemma]
(7) So, there exists m such that z=pm
(8) So, zn = vw = pkw = (pm)n = pnmn
(9) Dividing p from both sides gives us:
kw = p(n-1)mn
(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)mn = p(n-1)*V*w
(16) Dividing p(n-1) from both sides gives us:
Vw = mn
(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 = pnV 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
We proved that assuming that a relatively prime divisor of an n-power is not itself an n-power means that there must necessarily be a smaller relatively prime divisor that is also not an n-power and so on and so on.
Here is what Fermat wrote about Infinite Descent in a letter to another mathematician:
As he often did, Fermat left very few details on how to apply the method. He did provide one example of this method in his proof that the area of a right triangle cannot be equal to a square number. An elegant application of this proof is found in the case of FLT: n=4 where the proof rests on the method of infinite descent and the solution to Pythagorean Triples.
The basic method is very straight forward. One proves that if an assumption is true, it means that the assumption must also be true for an element that is smaller. In other words, an assumption leads to the proposition of an infinite number of cases where it is true.
This technique is especially useful in the domain of positive integers. In this case, infinite descent is impossible since it contradicts the Well Ordering Principle. In other words, there must always be a smallest element in any set of positive integers. But if there is a smallest element, then, there cannot be an infinite descent. In this way, the method can be used as way to prove by contradiction certain negative assumptions. It can also be used to prove a positive conclusion as I will show below.
Fermat is known to have used this technique to prove that there is no square equal to a right triangle. He left a proof using this technique for the case of n = 4 which I will go over in a future blog. He also wrote about its use in the proof for the case of n = 3 in a letter to Christian Huygens.
If Fermat had really found a proof for his theorem, it was without doubt based on this method.
To show the technique in action, I will use it to prove the following theorem:
Thereom: Relatively Prime Divisors of an n-power are themselves n-powers.
This theorem says that if gcd(v,w) = 1 and vw = zn
Then, there exists x,y such that v = xn, w = yn
(1) So, we start with gcd(v,w) = 1, vw = zn
(2) Assume that v is not equal to any number xn
(3) v ≠ 1 since 1 is an xn power
(4) Now, v is divisible by a prime number p. [Fundamental Theorem of Arithmetic]
(5) So, there exists k such that v = pk
(6) p divides z since zn = vw = pkw [By applying Euclid's Lemma]
(7) So, there exists m such that z=pm
(8) So, zn = vw = pkw = (pm)n = pnmn
(9) Dividing p from both sides gives us:
kw = p(n-1)mn
(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)mn = p(n-1)*V*w
(16) Dividing p(n-1) from both sides gives us:
Vw = mn
(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 = pnV 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
We proved that assuming that a relatively prime divisor of an n-power is not itself an n-power means that there must necessarily be a smaller relatively prime divisor that is also not an n-power and so on and so on.
Here is what Fermat wrote about Infinite Descent in a letter to another mathematician:
"As ordinary methods, such as are found in books, are inadequate
to proving such difficult propositions, I discovered at last
a most singular method...which I called the infinite descent.
At first I used it to prove only negative assertions, such as
'There is no right angled triangle in numbers whose area is a
square'... To apply it to affirmative questions is much harder,
so when I had to prove 'Every prime of the form 4n+1 is a sum
of two squares" I found myself in a sorry plight (en belle
peine). But at last such questions proved amenable to my methods."
-Quoted from Andre Weil's Number Theory
Saturday, May 07, 2005
Pythagorean Triples: Solution
OK, here's the solution for Diophantus's problem of determining the solution for:
x2 + y2 = z2
(1) We know that we can assume that x,y,z are coprime. [See my previous blog for details]
(2) The second important insight is that z has to be odd.
(a) Assume the opposite that z is even.
(b) Then, there exists another value Z such that z = 2 * Z
(c) Also, z2 is then divisible by 4 since:
z2 = (2 * Z)2 = 4 * (Z2)
(d) We know that x,y must both be odd because of (1).
(e) Since they are odd, there must also exist values X,Y such that:
x = 2 * X + 1
y = 2 * Y + 1
(f) But x2 + y2 cannot be divisible by 4 since:
x2 + y2 = (2 * X + 1)2 + (2 * Y + 1)2 =
= 4X2 + 4X + 1 + 4Y2 + 4Y + 1 =
= 4[ X2 + X + Y2 + Y ] + 2
(g) So, we have a contradiction and we reject our assumption.
(3) Since z is odd, either x or y must be even since an odd number is always the sum of an odd and an even number.
(4) Let's assume x is even. The same argument will also work if y is even.
(5) Now, we know that:
x2 = z2 - y2 = (z - y)(z + y)
(6) And, z - y and z + y must be even since z,y are odd.
(7) So, we know that there must exist u,v,w such that:
x = (2u)
z + y = (2v)
z - y = (2w)
(8) Which means that:
(2u)2 = (2v)(2w) [From (5) and (7)]
(9) Dividing both sides by 4 gives us:
u2 = v * w
(10) We need 1 more insight before the solution. Here it is: v,w are coprime
(a) Assume that v,w are not coprime.
(b) Then, there exists d such that d > 1 and d divides both v,w
(c) Then d divides both v + w and v - w
(d) But:
z + y + z - y =
2v + 2w
So 2z = 2v + 2w which means that z = v + w
So d divides z
(e) And:
z + y - (z - y) = 2v - 2w
So 2y = 2v - 2w which means that y = v - w
So d divides y
(f) Which is a contradiction since z,y are coprime [by (1)].
(g) So, we reject our assumption.
(11) By the properties of coprimes, we know from (9),(10) that v,w are themselves squares (see here for proof). [For those who need a review of coprimes, here is a link.]
(12) So, there exists p,q such that:
v = p2
w = q2
(13) And, we have our solution since:
z = v + w = p2 + q2
y = v - w = p2 - q2
x = 2u = 2pq [Since u2 = vw means u = pq]
We also know that:
(a) p,q are relatively prime. [Otherwise, z,x,y would not be relatively prime]
(b) p,q are opposite parity (that is, one is odd and one is even) [Since z is odd]
(14) For sure enough:
(p2 + q2)2 = (2pq)2 + (p2 - q2)2
(15) Now, to generate our answer, we can pick any p,q we want so long as they are integers.
For example, if p = 2 and q = 1, we get:
z = (2)2 + (1)2 = 5.
y = (2)2 - (1)2 = 3.
x = 2pq = 2*2*1 = 4
(16) We can do even better than this because we know that for each x,y,z, if they have common factors, the relation still holds.
z = d[p2 + q2]
y = d[p2 - q2]
x = d[2pq]
For example, if p = 2 and q = 1 and d = 2, we get:
z = (2)(5) = 10
y = (2)(3) = 6
x = (2)(4) = 8
And sure enough, 62 + 82 = 36 + 64 = 100.
QED
What's also nice about this result is that it is not too difficult to apply Fermat's method of infinite descent and prove Fermat's Last Theorem for n=4.
x2 + y2 = z2
(1) We know that we can assume that x,y,z are coprime. [See my previous blog for details]
(2) The second important insight is that z has to be odd.
(a) Assume the opposite that z is even.
(b) Then, there exists another value Z such that z = 2 * Z
(c) Also, z2 is then divisible by 4 since:
z2 = (2 * Z)2 = 4 * (Z2)
(d) We know that x,y must both be odd because of (1).
(e) Since they are odd, there must also exist values X,Y such that:
x = 2 * X + 1
y = 2 * Y + 1
(f) But x2 + y2 cannot be divisible by 4 since:
x2 + y2 = (2 * X + 1)2 + (2 * Y + 1)2 =
= 4X2 + 4X + 1 + 4Y2 + 4Y + 1 =
= 4[ X2 + X + Y2 + Y ] + 2
(g) So, we have a contradiction and we reject our assumption.
(3) Since z is odd, either x or y must be even since an odd number is always the sum of an odd and an even number.
(4) Let's assume x is even. The same argument will also work if y is even.
(5) Now, we know that:
x2 = z2 - y2 = (z - y)(z + y)
(6) And, z - y and z + y must be even since z,y are odd.
(7) So, we know that there must exist u,v,w such that:
x = (2u)
z + y = (2v)
z - y = (2w)
(8) Which means that:
(2u)2 = (2v)(2w) [From (5) and (7)]
(9) Dividing both sides by 4 gives us:
u2 = v * w
(10) We need 1 more insight before the solution. Here it is: v,w are coprime
(a) Assume that v,w are not coprime.
(b) Then, there exists d such that d > 1 and d divides both v,w
(c) Then d divides both v + w and v - w
(d) But:
z + y + z - y =
2v + 2w
So 2z = 2v + 2w which means that z = v + w
So d divides z
(e) And:
z + y - (z - y) = 2v - 2w
So 2y = 2v - 2w which means that y = v - w
So d divides y
(f) Which is a contradiction since z,y are coprime [by (1)].
(g) So, we reject our assumption.
(11) By the properties of coprimes, we know from (9),(10) that v,w are themselves squares (see here for proof). [For those who need a review of coprimes, here is a link.]
(12) So, there exists p,q such that:
v = p2
w = q2
(13) And, we have our solution since:
z = v + w = p2 + q2
y = v - w = p2 - q2
x = 2u = 2pq [Since u2 = vw means u = pq]
We also know that:
(a) p,q are relatively prime. [Otherwise, z,x,y would not be relatively prime]
(b) p,q are opposite parity (that is, one is odd and one is even) [Since z is odd]
(14) For sure enough:
(p2 + q2)2 = (2pq)2 + (p2 - q2)2
(15) Now, to generate our answer, we can pick any p,q we want so long as they are integers.
For example, if p = 2 and q = 1, we get:
z = (2)2 + (1)2 = 5.
y = (2)2 - (1)2 = 3.
x = 2pq = 2*2*1 = 4
(16) We can do even better than this because we know that for each x,y,z, if they have common factors, the relation still holds.
z = d[p2 + q2]
y = d[p2 - q2]
x = d[2pq]
For example, if p = 2 and q = 1 and d = 2, we get:
z = (2)(5) = 10
y = (2)(3) = 6
x = (2)(4) = 8
And sure enough, 62 + 82 = 36 + 64 = 100.
QED
What's also nice about this result is that it is not too difficult to apply Fermat's method of infinite descent and prove Fermat's Last Theorem for n=4.
Thursday, May 05, 2005
Coprime Numbers
In the last blog, I spoke about Diophantus's problem: to divide a square into the sum of two smaller squares.
In other words, to find solutions for x,y,z where:
x2 + y2 = z2.
The first step in solving this problem is to realize that we can assume that x,y,z are coprime (or another way to say it, relatively prime). That is, no two of these values are divisible by the same prime. So, if p is a prime that is a factor of x, then we know that it is not a factor of y and not a factor of z.
When we have a situation where the three numbers are not coprime (for example, 6,8,10), we will be able to divide out common factors and end up with three numbers that are.
In the case of 6,8,10, the three numbers share the prime 2. If we divide out 2, then we are left with 3,4,5 which are coprime.
This assumption is important because it greatly simplifies the task of analyzing the conditions for when a solution exists. In my next blog, I will show how this assumption gives us the solution to Diophantus's problem.
Interestingly, we can apply this same assumption to Fermat's Last Theorem. From this point on, we will only need to consider the case where x,y,z are relatively prime.
One of my goals in this project is to provide complete proofs each of the conclusions presented. This blog relies on one lemma. A lemma is an intermediate statement that requires proof and is used in a larger theorem.
Lemma: All solutions to xn + yn = zn can be reduced to a form where x,y,z are coprime. [Here is the proof.]
In other words, to find solutions for x,y,z where:
x2 + y2 = z2.
The first step in solving this problem is to realize that we can assume that x,y,z are coprime (or another way to say it, relatively prime). That is, no two of these values are divisible by the same prime. So, if p is a prime that is a factor of x, then we know that it is not a factor of y and not a factor of z.
When we have a situation where the three numbers are not coprime (for example, 6,8,10), we will be able to divide out common factors and end up with three numbers that are.
In the case of 6,8,10, the three numbers share the prime 2. If we divide out 2, then we are left with 3,4,5 which are coprime.
This assumption is important because it greatly simplifies the task of analyzing the conditions for when a solution exists. In my next blog, I will show how this assumption gives us the solution to Diophantus's problem.
Interestingly, we can apply this same assumption to Fermat's Last Theorem. From this point on, we will only need to consider the case where x,y,z are relatively prime.
One of my goals in this project is to provide complete proofs each of the conclusions presented. This blog relies on one lemma. A lemma is an intermediate statement that requires proof and is used in a larger theorem.
Lemma: All solutions to xn + yn = zn can be reduced to a form where x,y,z are coprime. [Here is the proof.]
Wednesday, May 04, 2005
Pythagorean Triples
When Fermat wrote his note in the margin, he was making a comment on the problem of determining Pythagorean Triples.
In Book II, Problem 8 of the Arithmetica, Diophantus poses the problem of how to divide a given square number into the sum of two smaller squares.
In other words, solve the problem:
x2 + y2 = z2.
Any three numbers that satisfy this equation are called Pythagorean Triples. They are called Pythagorean Triples since this is the same equation as the Pythagorean Theorem.
The Pythagorean Theorem is so well known that I refer people to this link if you would like to see a proof for it.
An example of a Pythagorean Triple is 3, 4, and 5 since 32 + 42 = 52.
I encourage everyone who has not already seen the solution to Diophantus's problem to try and solve it. This is without doubt what Fermat did and in solving this problem, he stumbled upon his famous generalization.
If you solve the problem, you should be able to prove there an infinite number of Pythagorean Triples and find a method for listing them out.
You can find the solution here.
This blog is based on the following sources:
In Book II, Problem 8 of the Arithmetica, Diophantus poses the problem of how to divide a given square number into the sum of two smaller squares.
In other words, solve the problem:
x2 + y2 = z2.
Any three numbers that satisfy this equation are called Pythagorean Triples. They are called Pythagorean Triples since this is the same equation as the Pythagorean Theorem.
The Pythagorean Theorem is so well known that I refer people to this link if you would like to see a proof for it.
An example of a Pythagorean Triple is 3, 4, and 5 since 32 + 42 = 52.
I encourage everyone who has not already seen the solution to Diophantus's problem to try and solve it. This is without doubt what Fermat did and in solving this problem, he stumbled upon his famous generalization.
If you solve the problem, you should be able to prove there an infinite number of Pythagorean Triples and find a method for listing them out.
You can find the solution here.
This blog is based on the following sources:
Subscribe to:
Posts (Atom)
