Monday, January 16, 2006

Fermat's Last Theorem: Proof for n=5: 2 is a prime in Z[(1 + √5)/2]

Today's blog continues the proof for Fermat's Last Theorem: n= 5. If you are interested in the history behind the proof, start here. If you are interested in the mathematical details behind the proof, start here.

Today's blog rests on a proof offered by Jody Esmonde and M. Ram Murty in Problems in Algebraic Number Theory.

To understand the details of today's proof, you will need to be familiar with Continued Fractions.

Lemma 1: if d = a2 + 1 and a ≥ 1, then the continued fraction expansion of √d is [a , 2a, ... ]

(1) a0 = a since a is less than a2 + 1 which is less than a + 1 since:

a =√a2
a + 1 = √a2 + 2a + 1

a2 is less than a2 + 1 is less than a2 + 2a + 1.

(2) a2 = 2a since 2a is less than 1/(√a2 + 1 - a) which is less than 2a + 1.

(a) 1/(√a2 + 1 - a) = (√a2 + 1 + a)/(a2 + 1 - a2) = √a2 + 1 + a.

(b) From (a), we see that 2a is less than a + √a2 + 1 since a2 + 1 is greater than a2.

(c) Since a2 + 1 is less than a2 + 2a + 1, we see that:

a2 + 1 + a is less than a + (a + 1) = a + √a2 + 2a + 1

(d) Finally, we see that all other items from this point ai are = 2a.

1/(√a2 + 1 + a - 2a) = 1/(√a2 + 1 - a) =
= (√a2 + 1 + a)/(a2 + 1 - a2) = √a2 + 1 + a.

QED

Lemma 2: if pk/qk is a convergent for the continued fraction expansion of α, then gcd(pk,qk) = 1.

(1) Let f be a factor that divides both pk and qk.

(2) We know that pkqk-1 - pk-1qk = (-1)k-1 (see Lemma 2 here)

(3) From (1), we know that f divides pkqk-1 - pk-1qk which means that f divides (-1)k-1

(4) But the only way that f divides (-1)k-1 is if f = 1 since all values are integers.

QED

Lemma 3:
If:
(a) α is an irrational number
(b) r,s are integers
(c) s is greater than 0
(d) absolute(sα - r) is less than absolute(qkα - pk) where pk,qk are the convergents of the continued fraction expansion of α
Then:
s ≥ qk+1

Proof:

(1) Assume that 1 ≤ s which is less than qk+1

(2) Then, there exist x,y such that:
pkx + pk+1y = r
qkx + qk+1y = s

(3) Multiplying qk to the first equation and pk to the second gives us:
pkqkx + pk+1qky = rqk
pkqkx + pkqk+1y = spk

(4) Now, subtracting the second from the first gives us:

y(pk+1qk - pkqk+1) = rqk - spk

(5) Multiplying qk+1 to the first equation in #2 and pk+1 to the second equation and then subtracting gives us:

x(pkqk+1 - pk+1qk) = rqk+1 - spk+1

(6) Applying a previous result (see Lemma 2 here), we get:
x = (-1)k(spk+1 - rqk+1)
y = (-1)k(rqk - spk)

(7) We know that x ≠ 0

(a) Assume x = 0

(b) r/s = pkk+1/qk+1 from #2.

(c) We know that gcd(pk+1,qk+1)=1 from Lemma 2 above.

(d) So from (b), r(qk+1) = s(pk+1) and from (c), we know that:
qk+1 must divide s.

(e) But since s is greater than 0, this means that qk+1 ≤ s which contradicts our assumption at #1 so we can reject (7a).

(8) We know that y ≠ 0

(a) Assume that y = 0

(b) Then r = pkx

(c) Then s = qkx

(d) So that absolute(sα - r) = absolute(x) * absolute(qkα - pk)

(e) Because x ≠ 0, we then have absolute(x) * absolute(qkα-pk) ≥ absolute(qkα - pk)

(f) But combining (d) with (e) gives us:
absolute(sα - r) ≥ absolute(qkα - pk) which contradicts our original assumption (d) in the lemma statement.

(g) Therefore, we reject (8a).

(9) x,y have opposite signs (one is positive and one is negative)

(a) Assume y is negative then qkx = s - qk+1y. Since qi ≥ 0 (see Corollary 4.1 here) and since s ≥ 1, x is positive.

(b) Assume that y is positive, then qk+1y ≥ qk+1 which is greater than s (by assumption #1) so qkx = s - qk+1y is less than 0.

(10) We know that α lies in between consecutive convergents since:

(a) By a previous result (see Corollary 5.2 here), we know that if k is even:

pk/qk is less than α which is less (pk+1)/qk+1

Which means that pk is less than αqk and that αqk+1 is less than pk+1.

This then gives us that:
qkα - pk is positive and qk+1α - pk+1 is negative.

(b) We also know that if k is odd,

(pk+1)/qk+1 is less than α which is less than pk/qk

Which means that pk+1 is less than αqk+1 and qk+1α is less than pk.

This then gives us that:
qk+1α - pk+1 is positive and qkα - pk is negative.

(11) By 10(a) and 10(b), we know that regardless of whether k is odd or even, qkα - pk and qk+1α - pk+1 have opposite signs.

(12) This means that x(qkα - pk) and y(qk+1α - pk+1) have the same sign.

(13) Finally, this gives us that:

absolute(sα - r) =
= absolute( [qkx + qk+1y]α - [pkx + pk+1y]) =
= absolute( x[qkα - pk] + y[qk+1α - pk+1] )

(14) This then gives us:

absolute(sα - r) ≥ absolute(x)*absolute(qkα - pk) + absolute(y)*absolute(qk+1α - pk+1) ==>
absolute(sα - r) ≥ absolute(x)*absolute(qkα - pk) ==>
absolute(sα - r) ≥ absolute(qkα - pk)

(15) But this contradicts #1 so we are done.

QED

Lemma 4: 1 ≤ s is less than qk+1, then absolute(qkα - pk) ≤ absolute(sα - r).

(1) Assume that absolute(sα - r) is less than absolute(qkα - pk)

(2) Then s ≥ qk+1

(3) But s is less than qk+1

(4) So we have a contradiction and we reject our assumption.

QED

Lemma 5: if absolute(α - r/s) is less than 1/(2s2) and s is greater than 0, then r/s is a convergent of the continued fraction of α

(1) Assume that r/s is not a convergent of α

(2) Then, r/s ≠ pn/qn for all n.

(3) Since q0 = 1 and qk ≥ k (see Corollary 4.1 here), we may define a value k such that:

qk ≤ s which is less than qk+1

(4) So we also have qk ≤ s is less than qk+1

(5) absolute(α - r/s) is less than 1/(2s2) implies that:
absolute(sα - r) is less than 1/2s.

(6) From a result in Lemma 4 above, absolute(qkα - pk) ≤ absolute(sα - r).

Which then gives us:
absolute(qk α - pk) is less than 1/2s.

(7) Dividing all sides by qk gives:
absolute(α - pk/qk) is less than 1/(2sqk)

(8) Since r/s ≠ pk/qk, absolute(spk - rqk) ≥ 1.

(9) This means that:

1/(sqk) ≤ absolute(spk - rqk)/sqk =
= absolute(pk/qk - r/s) =
= absolute(pk/qk - r/s + α - α )

which is:

≤ absolute(α - pk/qk) + absolute(α - r/s)

which is less than:

1/(2sqk) + 1/2s2

(10) Putting it all together gives us:

1/sqk is less than 1/(2sqk) + 1/(2s2)

(11) Subtracting 1/2qk from both sides gives us:

1/(2sqk) is less than 1/(2s2).

(12) But this means that:

qk is greater than s.

(13) This is a contradiction so we reject our assumption #1.

QED

Lemma 6: if x2 - dy2 is positive and is less than √d, then x,y is a convergent to the continued fraction expansion of √d.

(1) By our assumption above:
x2 - dy2 = (x + y√d)(x - y√d) is greater than 0.

(2) This means that x > y√d (otherwise, the value in #1 would be negative since x,y are positive numbers)

(3) So x/y is greater thand

(4) So absolute(x/y - √d) = (x - y√d)/y =

= (x2 - dy2)/[y(x + y√d)]

(5) This is less than:

(x2 - dy2)/[y(2y√d)] since x is greater than y√d and y(x + y√d) is greater than y(y√d + y√d) = y(2y√d)

(6) And (x2 - dy2)/y(2y√d) is less than d/y(2y√d) [By the assumption of this lemma]

(7) Dividing both sides by d gives us:

x/y - √d is less than 1/(2y2)

(8) Which by Lemma 5 above gives us our conclusion.

QED

Lemma 7: if x2 - dy2 is a negative number greater than -√d, then x,y are convergents in the continued fraction expansion of √d.

(1) y2 - (1/d)x2 is a positive number less than 1/√d since:

(a) d is greater than dy2 - x2 (By multiplying by -1 to the assumption)

(b) d/d is greater than y2 - (x2)/d which is greater than 0.

(c) 1/√d is greater than y2 -(x2)/d which is greater than 0.

(2) y is greater than x/√d since:

(a) (y - x/√d)(y + x/√d) is greater than 0.

(b) if y were less than this same value would be negative.

(c) if y = x/√d then (2a) would = 0 which it does not.

(3) From #2, y/x is greater than 1/√d.

(4) y/x - 1/√d = (y -x/√d)/x =

= [y2 - x2/d]/[x(y + x/√d)]

which is less than:

[y2 - x2/d]/(2x2/√d) since:

(a) y is greater than x/√d (from #2 above) so xy is greater than x2/√d.

(b) And xy + x2/√d is greater than 2x2/√d.

(5) Now:
y2 - (x2/d) is less than 1/√d (from #1) so:

(y2 - x2/√d)/(2x2/√d) is less than: (1/√d)/(2x2/√d)

(6) Since:

(1/√d)/(2x2/√d) = 1/2x2, we have the following:
y/x - 1/√d is less than 1/2x2.

(7) By the lemma above, y/x is a convergent.

Lemma 8: if d = a2 + 1 and absolute(u2 - dv2) ≠ 0,1, then absolute(u2 - dv2) is greater than √d

(1) The continued fraction for a2 + 1 is [ a, 2a ... ] (see Lemma 1 above)

(2) This means that the period = 1 starting at 1.

(3) From a previous result, this means that for all convergents:
pk2 - dq2 = (-1)k

(4) Now if absolute(u2 - dv2) is less than d, then u,v are convergents since:

(a) If u2 - dv2 is less than d, then from Lemma 6 above, u,v are convergents.

(b) If -(u2 - dv2) is less than d, then from Lemma 7 above, u,v are convergents.

(5) From #4, since we are assuming that absolute(u2 - dv2) ≠ 1 or 0, then we can conclude that:

absolute(u2 - dv2) is greater than d.

QED

Lemma 9: 2 is a prime in Z[(1 + √5)/2]

(1) Norm(2) = [(4 + 0)/2]*[(4 + 0)/2] = 16/4 = 4

(2) Let's assume that 2 is not a prime.

(3) Then there exists two values a,b that are not units Norm(a) * Norm(b) = Norm(2) = ±4.

(4) Since a,b are not units, we can assume that there norm(a), norm(b) ≠ ± 1.

(5) This limits us to consider Norm(a) = ± 2 and Norm(b) = ± 2.

(6) If Norm(a) = ± 2, then

Norm(a) = [(a + b√5)/2][(a - b√5)/2] = (a2 - 5b2)/4

(7) This means that:

(a2 - 5b2)/4 = ± 2 which implies that a2 - 5b2 = ± 8.

(8) We know from properties of Z[(a + b√5)/2] that a,b have the same parity (see here)

(9) First, we note that they cannot be both even.

(a) Assume that u,v are both even

(b) Then there exists u,v such that:
a = 2u
b = 2v

(c) (2u)2 - 5(2v)2 = ± 8

So:

4u2 -20v2 = 4(u2 - 5v2) = ± 8

And:

u2 - 5v2 = ± 2.

(d) But absolute(u2 - 5v2) ≠ ± 2 from Lemma 8 above since 5 = 22 + 1.

(e) So we reject our assumption and conclude that a,b are both odd.

(10) But they cannot both be odd since:

(a) Assume they are both odd.

(b) Then, there exist u,v such that:
a = 2u + 1
b = 2v + 1

(c) (2u+1)2 - 5(2v+1)2 = 4u2 + 4u + 1 - 5(4v2 + 4v + 1) =
= 4u2 + 4u + 1 - 20v2 -20v - 5 =
= 4u2 - 4u - 4 - 20v2 - 20v =
= 4(u2 + u - 1 - 5v2 - 5v) = ± 8

(d) So we can conclude that:
u2 + u - 1 -5v2 - 5v = ± 2

And:
u(u+1) - 5v(v+1) - 1 = ± 2

(e) But we know that u(u+1) is even and 5v(v+1) is even.

We know they are even since either x or x+1 is even and even * odd = even.

(f) But this means that #10d is impossible since

even - even - odd = odd

(g) So we have again found a contradiction.

(11) But it is impossible that a,b are neither odd nor even so we again have an impossibility and we reject our assumption.

QED

8 comments:

  1. In step (10a) of Lemma there is an incorrect link.

    Rob

    ReplyDelete
  2. In step (10) of Lemma 5:

    Should
    1/sqk is less than 1/(2qk)+1/(2s^2)

    be
    1/sqk is less than 1/(2sqk)+1/(2s^2)


    And in step (11) of Lemma 5:

    Should
    Subtracting 1/2qk from both sides gives us:
    1/(sqk) is less than 1/(2s^2).

    be
    Subtracting 1/2sqk from both sides gives us:
    1/(2sqk) is less than 1/(2s^2).

    ReplyDelete
  3. In step (3) of Lemma 8:

    Should

    pk^2+dq^2=(-1)^k

    be

    pk^2-dqk^2=(-1)^k

    Rob

    ReplyDelete
  4. Hi Scouse Rob,

    Thanks very much for the corrections! I've fixed all the typos that you mentioned on this page. :-)

    Cheers,

    -Larry

    ReplyDelete
  5. Larry

    Please help, I am stuck.

    In step (3) of Lemma 8:

    From a previous result, this means that for all convergents:
    pk^2-dqk^2=(-1)^k

    I cannot find the previous result that shows this fact.

    Rob

    ReplyDelete
  6. Hi Scouse Rob,

    This looks like a bad link. I'm also having trouble finding the previous result.

    I'll add the correct result over the next few days.

    It comes from page 265-266 (Ex. 8.2.8) of Jody Esmonde and M. Ram Murty's Problems in Algebraic Theory.

    -Larry

    ReplyDelete
  7. I found the Esmonde proof, thanks.

    In Lemma 9 step (9a):

    Assume that u,v are both even

    should be

    Assume that a,b are both even

    Rob

    ReplyDelete
  8. In Lemma 9 step (9a)

    Assume that u,v are both even

    should be:

    Assume that a,b are both even

    Rob

    ReplyDelete