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]
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:
(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:

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.
(7) But this means there exists A,B,C such that:
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.

(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

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
(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):
(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