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 than √d
(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
Monday, January 16, 2006
Fermat's Last Theorem: Proof for n = 5: Key Lemma 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 the proof offered by Paulo Ribenboim in Fermat's Last Theorem for Amateurs.
Lemma 1: Given a,b such that:
(a) gcd(a,b)=1
(b) a ≡ b (mod 2)
(c) a,b are nonzero
(d) 5 doesn't divide a
(e) 5 divides b
(f) (a + b√5)/2 = [(m + n√5)/2]5([t+u√5]/2) where u = 0.
Then:
(a) a = c(c4 + 50c2d2 + 125d4)/16
(b) b = 5d(c4 + 10c2d2 + 5d4)/16
(c) gcd(c,d)=1
(d) c,d have different parities
(e) 5 doesn't divide c
(f) c,d are nonzero
Proof:
(1) t2 - 5u2 = ± 4 since [t+u√5]/2 is a unit.
(2) Since u = 0, t = ± 2 so t/2 = ± 1.
(3) Let c = ±m, d = ± n
(4) We now have:
(a + b√5)/2 = ±[(c + d√5)/2]5.
(5) a + b√5 = (c5 + 5c4d√5 + 50c3d2 + 50c2d3√5 + 125cd4 + 25d5√5)/16
(6) So that:
a = (c5 + 50c3d2 + 125cd4)/16 = c(c4 + 50c2d2 + 125d4)/16
b = (5c4d + 50c2d3 + 25d5)/16 = 5d(c4 + 10c2d10 + 5d4)/16
(7) gcd(c,d)=1 since c divides a, d divides b, and gcd(a,b) = 1.
(8) c,d are odd since a,b are both odd (since c divides a and d divides b)
(9) 5 doesn't divide c since 5 doesn't divide a.
QED
Lemma 2: Given a,b such that:
(a) gcd(a,b)=1
(b) a ≡ b (mod 2)
(c) a,b are nonzero
(d) 5 doesn't divide a
(e) 5 divides b
(f) (a + b√5)/2 = [(m + n√5)/2]5([t+u√5]/2) where u ≠ 0.
Then:
(a) a = c(c4 + 50c2d2 + 125d4)/16
(b) b = 5d(c4 + 10c2d2 + 5d4)/16
(c) gcd(c,d)=1
(d) c,d have different parities
(e) 5 doesn't divide c
(f) c,d are nonzero
Proof:
(1) We know that t2 - 5u2 = ± 4 since it is a unit.
(2) We know that we can assume that;
(t + u√5)/2 = ±[(1 ± √5 )/2]e where e is ≥ 2 and 5 divides e (see the reasoning in Lemma 3 here)
(3) This means that we can define c,d such that:
(c + d√5)/2 = ±([m + n√5]/2)([1 ± √5]/2)f
(4) This gives us:
(a + b√5)/2 = [(c + d√5)/2]5
(5) We can then follow the logic from step #4 in Lemma 1 above.
QED
Today's blog rests on the proof offered by Paulo Ribenboim in Fermat's Last Theorem for Amateurs.
Lemma 1: Given a,b such that:
(a) gcd(a,b)=1
(b) a ≡ b (mod 2)
(c) a,b are nonzero
(d) 5 doesn't divide a
(e) 5 divides b
(f) (a + b√5)/2 = [(m + n√5)/2]5([t+u√5]/2) where u = 0.
Then:
(a) a = c(c4 + 50c2d2 + 125d4)/16
(b) b = 5d(c4 + 10c2d2 + 5d4)/16
(c) gcd(c,d)=1
(d) c,d have different parities
(e) 5 doesn't divide c
(f) c,d are nonzero
Proof:
(1) t2 - 5u2 = ± 4 since [t+u√5]/2 is a unit.
(2) Since u = 0, t = ± 2 so t/2 = ± 1.
(3) Let c = ±m, d = ± n
(4) We now have:
(a + b√5)/2 = ±[(c + d√5)/2]5.
(5) a + b√5 = (c5 + 5c4d√5 + 50c3d2 + 50c2d3√5 + 125cd4 + 25d5√5)/16
(6) So that:
a = (c5 + 50c3d2 + 125cd4)/16 = c(c4 + 50c2d2 + 125d4)/16
b = (5c4d + 50c2d3 + 25d5)/16 = 5d(c4 + 10c2d10 + 5d4)/16
(7) gcd(c,d)=1 since c divides a, d divides b, and gcd(a,b) = 1.
(8) c,d are odd since a,b are both odd (since c divides a and d divides b)
(9) 5 doesn't divide c since 5 doesn't divide a.
QED
Lemma 2: Given a,b such that:
(a) gcd(a,b)=1
(b) a ≡ b (mod 2)
(c) a,b are nonzero
(d) 5 doesn't divide a
(e) 5 divides b
(f) (a + b√5)/2 = [(m + n√5)/2]5([t+u√5]/2) where u ≠ 0.
Then:
(a) a = c(c4 + 50c2d2 + 125d4)/16
(b) b = 5d(c4 + 10c2d2 + 5d4)/16
(c) gcd(c,d)=1
(d) c,d have different parities
(e) 5 doesn't divide c
(f) c,d are nonzero
Proof:
(1) We know that t2 - 5u2 = ± 4 since it is a unit.
(2) We know that we can assume that;
(t + u√5)/2 = ±[(1 ± √5 )/2]e where e is ≥ 2 and 5 divides e (see the reasoning in Lemma 3 here)
(3) This means that we can define c,d such that:
(c + d√5)/2 = ±([m + n√5]/2)([1 ± √5]/2)f
(4) This gives us:
(a + b√5)/2 = [(c + d√5)/2]5
(5) We can then follow the logic from step #4 in Lemma 1 above.
QED
Sunday, January 15, 2006
Fermat's Last Theorem: Proof for n=5: Key Lemma 1
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 the proof offered by Paulo Ribenboim in Fermat's Last Theorem for Amateurs.
Lemma 1: Given a,b,x such that:
(a) a,b,x are integers
(b) a,b have different parities
(c) gcd(a,b)=1
(d) a,b are nonzero
(e) 5 doesn't divide a
(f) 5 divides b
(g) a2 - 5b2 = x5
(h) there exist integers h,k such that: a + b√5 = ([h + k√5]/2)5
(i) h,k have the same parity
Then h,k are even.
(1) 25b = 5k(h4 + 10h2k2 + 5k4) since:
(a) (h + k√5)5 = h5 + 5h4k√5 + 50h3k2 + 50h2k3√5 + 125hk4 + 25k5√5.
(b) From (a) and from (h) above: 25b = 5h4k + 50h2k3 + 25k5 [25 is necessary since a + b√5 = [h + k√5] divided by 25
(c) From (b), 25b = 5k(h4 + 10h2k2 + 5k4)
(2) Assume that h,k are odd
(3) From (c), we know that 32 must divide (h4 + 10h2k2 + 5k4) since 2 doesn't divide 5 and since 2 doesn't divide k (since we are assuming in #2 that k is odd)
(4) h4 or k4 ≡ 1 or 17 (mod 32) since (the argument for h below applies equally to k):
(a) h is odd so h ≡ 1 (mod 2) which means that h modulo 32 could be any odd number including ±1, ± 3, ± 5, and so on until ± 15.
(b) h2 modulo 32 can only be congruent to 1, 9, 17, or 25 (see here for a review of modular arithmetic)
(±1)2 ≡ 1 (mod 32)
(±3)2 ≡ 9 (mod 32)
(±5)2 ≡ 25 (mod 32)
(±7)2 ≡ 49 ≡ 17 (mod 32)
(±9)2 ≡ 81 ≡ 17 (mod 32)
(±11)2 ≡ 121 ≡ 25 (mod 32)
(±13)2 ≡ 169 ≡ 9 (mod 32)
(±15)2 ≡ 225 ≡ 1 (mod 32)
(c) h4 modulo 32 can only be congruent 1 or 17.
(1)2 ≡ 1 (mod 32)
(9)2 ≡ 17 (mod 32)
(17)2 ≡ 289 ≡ 1 (mod 32)
(25)2 ≡ 625 ≡ 17 (mod 32)
(5) For h4 ≡ 1 (mod 32), we know that h2 ≡ 1 or 17 (mod 32)
(6) For h4 ≡ 17 (mod 32), we know that h2 ≡ 9 or 25.
(7) But from our assumption in #2, we find that 32 cannot divide (h4 + 10h2k2 + 5k4) since modulo 32 it is congruent to 16 (see below)
Case h4 ≡ 1, k4 ≡ 1:
(1) + 10(1)(1) + 5(1) ≡ 1 + 10 + 5 ≡ 16 (mod 32)
(1) + 10(17)(1) + 5(1) ≡ 1 + 170 + 5 ≡ 1 + 10 + 5 ≡ 16 (mod 32)
(1) + 10(1)(17) + 5(1) ≡ 1 + 170 + 5 ≡ 1 + 10 + 5 ≡ 16 (mod 32)
(1) + 10(17)(17) + 5(1) ≡ 1 + 2890 + 5 ≡ 1 + 10 + 5 ≡ 16 (mod 32)
Case h4 ≡ 17, k4 ≡ 1:
(17) + 10(9)(1) + 5(1) ≡ 17 + 90 + 5 ≡ 17 + 26 + 5 ≡ 16 (mod 32)
(17) + 10(25)(1) + 5(1) ≡ 17 + 250 + 5 &eqiuv; 17 + 26 + 5 ≡ 16 (mod 32)
(17) + 10(9)(17) + 5(1) ≡ 17 + 1530 + 5 ≡ 17 + 26 + 5 ≡ 16 (mod 32)
(17) + 10(25)(17) + 5(1) ≡ 17 + 4250 + 5 ≡ 17 + 26 + 5 ≡ 16 (mod 32)
Case h4 ≡ 1, k4 ≡ 17:
(1) + 10(1)(9) + 5(17) ≡ 1 + 90 + 85 ≡ 1 + 26 + 21 & equiv; 16 (mod 32)
(1) + 10(17)(9) + 5(17) ≡ 1 + 1530 + 85 ≡ 1 + 26 + 21 & equiv; 16 (mod 32)
(1) + 10(1)(25) + 5(17) ≡ 1 + 250 + 85 &eqiuv; 1 + 26 + 21 ≡ 16 (mod 32)
(1) + 10(17)(25) + 5(17) ≡ 1 + 4250 + 85 ≡ 1 + 26 + 21 & equiv; 16 (mod 32)
Case h4 ≡ 17, k4 equiv; 17
(17) + 10(9)(9) + 5(17) ≡ 17 + 810 + 85 ≡ 17 + 10 + 21 ≡ 16 (mod 32)
(17) + 10(25)(9) + 5(17) ≡ 17 + 2250 + 85 ≡ 17 + 10 + 21 ≡ 16 (mod 32)
(17) + 10(9)(25) + 5(17) ≡ 17 + 2250 + 85 ≡ 17 + 10 + 21 ≡ 16 (mod 32)
(17) + 10(25)(25) + 5(17) ≡ 17 + 6250 + 85 ≡ 17 + 10 + 21 ≡ 16 (mod 32)
(8) So we have a contradiction and we reject our assumption.
QED
Lemma 2: Given a,b such that:
(a) gcd(a,b)=1
(b) a,b have different parities (one is odd, one is even)
(c) a,b are nonzero
(d) 5 doesn't divide a
(e) 5 divides b
(f) a + b√5 = [(m + n√5)/2]5([t+u√5]/2) where u = 0.
Then:
(a) a = c(c4 + 50c2d2 + 125d4)
(b) b = 5d(c4 + 10c2d2 + 5d4)
(c) gcd(c,d)=1
(d) c,d have different parities
(e) 5 doesn't divide c
(f) c,d are nonzero
Proof:
(1) We know that there exists m',n' such that:
(m' + n'√5)/2 = [(m+n√5)/2]5= (m5 + 5m4n√5 + 50m3n2 + 50m2n3√5 + 125mn4 + 25n5√5)/25
(2) So, m' = (m5 + 50m3n2 + 125mn4)/24
(3) This means that 16m' ≡ m5 (mod 5)
(4) So, n' = (5m4n + 50m2n3 + 25n5)/24
(5) This means that 16n' ≡ 0 (mod 5) and 5 divides n'.
(6) a + b√5 = [(m' + n'√5)/2][(t + u√5)/2] = (m't + m'u√5 + n't√5 + 5n'u)/4
(7) So:
4a = m't + 5n'u
4b = m'u + n't
(8) From this we can conclude that 5 doesn't divide m' (otherwise from #7, 5 would divide a which it does not)
(9) We can also conclude that 5 doesn't divide m (otherwise from #3, 5 woud divide m' which from #8 it does not)
(10) From #7, we know that 5 divides u (since it divides 4b, n't but doesn't divide m')
(11) We also know that t = ± 2 since u = 0 and (t + u√5)/2 is a unit.
(12) From #11, we know that a + b√5 = ± [(m + n√5)/2]5
(13) From #12 and Lemma 1 above and the fact that m ≡ n (mod 2), we can conclude that m,n are even.
(14) Let:
c = ±m/2
d = ±n/2
(15) a + b√5 = ±(c + d√5)5 = c5 + 5c4d√5 + 50c3d2 + 50c2d3√5 + 125cd4 + 25d5√5.
(16) So:
a = c5 + 50c3c2 + 125cd4 = c(c4 + 50c2d2 + 125d4)
b = 5c4d + 50c2d3 + 25d5 = 5d(c4 + 10c2d2 + 5d4)
(17) gcd(c,d) = 1 since c divides a, d divides b. If gcd(c,d) ≠ 1 then it would mean a,b have a common factor which they don't.
(18) c,d have different parities
(a) c,d cannot both be even since gcd(c,d)=1 from #17
(b) c,d cannot both be odd since from #16:
a = odd(odd + even + odd) = odd(even) = even
b = odd(odd + even + odd) = odd(even) = even
Which is impossible since a,b have different parities.
(c) Therefore c,d have different parities too.
(19) 5 doesn't divide c since 5 doesn't divide m from #9.
(20) Finally, we know that c,d are nonzero since:
(a) c is nonzero from #16 since a is nonzero
(b) d is nonzero from #16 since b is nonzero
QED
Lemma 3: Given a,b such that:
(a) gcd(a,b)=1
(b) a,b have different parities (one is odd, one is even)
(c) a,b are nonzero
(d) 5 doesn't divide a
(e) 5 divides b
(f) a + b√5 = [(m + n√5)/2]5([t+u√5]/2) where u ≠ 0.
Then:
(a) a = c(c4 + 50c2d2 + 125d4)
(b) b = 5d(c4 + 10c2d2 + 5d4)
(c) gcd(c,d)=1
(d) c,d have different parities
(e) 5 doesn't divide c
(f) c,d are nonzero
Proof:
(1) Since [t+u√5]/2 is a unit, we know that there exists an integer e (see here) such that:
[t+u√5]/2 = ±([1 + √5]/2)e
(2) By our assumption that u ≠ 0, we know that e ≠ 0
(3) We can assume that e is positive, since we make e positive by replacing [1 + √5]/2 with its inverse -(1 - √5)/2 since:
(a) [(1 + √5)/2]-1 = 2/(1 + √5) = 2(1 - √5)/(1 - 5) = (2 - 2√5)/(-4) = (1 - √5)/(-2) = -(1 - √5)/2
(b) [(1 + √5)/2]-e = ([(1 + √5)/2]-1)e = [-(1 - √5)/2 ]e
(4) We know that e is ≥ 2 since:
(a) Since 5 divides b, it must divide u (see the reasoning in lemma 2)
(b) But if e = 1, then u = ±1 which is not divisible by 5.
(5) So, we can assume that (t + u√5)/2 = [±(1 √5)e]/(2e)
(6) Which implies that:
±(2e-1)(t + u√5) = (1 ± √5)e
(7) Using the binomial theorem (see here), we see that 2e-1u ≡ ±e (mod 5) since:
(1 ± √5)e = 1 + e√5 + [e*(e-1)]5 + [e*(e-1)(e-2)](5)√5 + ... + (√5)e
Since e ≥ 2, we know that all other value but the second one are divisible by 5.
(8) Since 5 divides u (from #4a), we know that e ≡ 0 (mod 5) so that 5 divides e.
(9) Then there must exist f such that e = 5f.
(10) We can assume that there exist c',d' such that:
(c' + d'√5)/2 = [(m + n√5)/2][(1 ± √5)/2]f
(11) From this we know that:
a + b√5 = [(c' + d'√5)/2]
(12) We further know that c', d' have the same parity (because of the nature of Z[(1 + √5)/2]) so that we can assume that they are even from Lemma 1 above.
(13) This allows us to suppose there c,d such that:
c = ±c'/2, d = ±d'/2
(14) We now have the equation:
a + b√5 = ±(c + d√5)5
(15) This allows to follow the same logic from Lemma 2, starting at step #15.
QED
Today's blog rests on the proof offered by Paulo Ribenboim in Fermat's Last Theorem for Amateurs.
Lemma 1: Given a,b,x such that:
(a) a,b,x are integers
(b) a,b have different parities
(c) gcd(a,b)=1
(d) a,b are nonzero
(e) 5 doesn't divide a
(f) 5 divides b
(g) a2 - 5b2 = x5
(h) there exist integers h,k such that: a + b√5 = ([h + k√5]/2)5
(i) h,k have the same parity
Then h,k are even.
(1) 25b = 5k(h4 + 10h2k2 + 5k4) since:
(a) (h + k√5)5 = h5 + 5h4k√5 + 50h3k2 + 50h2k3√5 + 125hk4 + 25k5√5.
(b) From (a) and from (h) above: 25b = 5h4k + 50h2k3 + 25k5 [25 is necessary since a + b√5 = [h + k√5] divided by 25
(c) From (b), 25b = 5k(h4 + 10h2k2 + 5k4)
(2) Assume that h,k are odd
(3) From (c), we know that 32 must divide (h4 + 10h2k2 + 5k4) since 2 doesn't divide 5 and since 2 doesn't divide k (since we are assuming in #2 that k is odd)
(4) h4 or k4 ≡ 1 or 17 (mod 32) since (the argument for h below applies equally to k):
(a) h is odd so h ≡ 1 (mod 2) which means that h modulo 32 could be any odd number including ±1, ± 3, ± 5, and so on until ± 15.
(b) h2 modulo 32 can only be congruent to 1, 9, 17, or 25 (see here for a review of modular arithmetic)
(±1)2 ≡ 1 (mod 32)
(±3)2 ≡ 9 (mod 32)
(±5)2 ≡ 25 (mod 32)
(±7)2 ≡ 49 ≡ 17 (mod 32)
(±9)2 ≡ 81 ≡ 17 (mod 32)
(±11)2 ≡ 121 ≡ 25 (mod 32)
(±13)2 ≡ 169 ≡ 9 (mod 32)
(±15)2 ≡ 225 ≡ 1 (mod 32)
(c) h4 modulo 32 can only be congruent 1 or 17.
(1)2 ≡ 1 (mod 32)
(9)2 ≡ 17 (mod 32)
(17)2 ≡ 289 ≡ 1 (mod 32)
(25)2 ≡ 625 ≡ 17 (mod 32)
(5) For h4 ≡ 1 (mod 32), we know that h2 ≡ 1 or 17 (mod 32)
(6) For h4 ≡ 17 (mod 32), we know that h2 ≡ 9 or 25.
(7) But from our assumption in #2, we find that 32 cannot divide (h4 + 10h2k2 + 5k4) since modulo 32 it is congruent to 16 (see below)
Case h4 ≡ 1, k4 ≡ 1:
(1) + 10(1)(1) + 5(1) ≡ 1 + 10 + 5 ≡ 16 (mod 32)
(1) + 10(17)(1) + 5(1) ≡ 1 + 170 + 5 ≡ 1 + 10 + 5 ≡ 16 (mod 32)
(1) + 10(1)(17) + 5(1) ≡ 1 + 170 + 5 ≡ 1 + 10 + 5 ≡ 16 (mod 32)
(1) + 10(17)(17) + 5(1) ≡ 1 + 2890 + 5 ≡ 1 + 10 + 5 ≡ 16 (mod 32)
Case h4 ≡ 17, k4 ≡ 1:
(17) + 10(9)(1) + 5(1) ≡ 17 + 90 + 5 ≡ 17 + 26 + 5 ≡ 16 (mod 32)
(17) + 10(25)(1) + 5(1) ≡ 17 + 250 + 5 &eqiuv; 17 + 26 + 5 ≡ 16 (mod 32)
(17) + 10(9)(17) + 5(1) ≡ 17 + 1530 + 5 ≡ 17 + 26 + 5 ≡ 16 (mod 32)
(17) + 10(25)(17) + 5(1) ≡ 17 + 4250 + 5 ≡ 17 + 26 + 5 ≡ 16 (mod 32)
Case h4 ≡ 1, k4 ≡ 17:
(1) + 10(1)(9) + 5(17) ≡ 1 + 90 + 85 ≡ 1 + 26 + 21 & equiv; 16 (mod 32)
(1) + 10(17)(9) + 5(17) ≡ 1 + 1530 + 85 ≡ 1 + 26 + 21 & equiv; 16 (mod 32)
(1) + 10(1)(25) + 5(17) ≡ 1 + 250 + 85 &eqiuv; 1 + 26 + 21 ≡ 16 (mod 32)
(1) + 10(17)(25) + 5(17) ≡ 1 + 4250 + 85 ≡ 1 + 26 + 21 & equiv; 16 (mod 32)
Case h4 ≡ 17, k4 equiv; 17
(17) + 10(9)(9) + 5(17) ≡ 17 + 810 + 85 ≡ 17 + 10 + 21 ≡ 16 (mod 32)
(17) + 10(25)(9) + 5(17) ≡ 17 + 2250 + 85 ≡ 17 + 10 + 21 ≡ 16 (mod 32)
(17) + 10(9)(25) + 5(17) ≡ 17 + 2250 + 85 ≡ 17 + 10 + 21 ≡ 16 (mod 32)
(17) + 10(25)(25) + 5(17) ≡ 17 + 6250 + 85 ≡ 17 + 10 + 21 ≡ 16 (mod 32)
(8) So we have a contradiction and we reject our assumption.
QED
Lemma 2: Given a,b such that:
(a) gcd(a,b)=1
(b) a,b have different parities (one is odd, one is even)
(c) a,b are nonzero
(d) 5 doesn't divide a
(e) 5 divides b
(f) a + b√5 = [(m + n√5)/2]5([t+u√5]/2) where u = 0.
Then:
(a) a = c(c4 + 50c2d2 + 125d4)
(b) b = 5d(c4 + 10c2d2 + 5d4)
(c) gcd(c,d)=1
(d) c,d have different parities
(e) 5 doesn't divide c
(f) c,d are nonzero
Proof:
(1) We know that there exists m',n' such that:
(m' + n'√5)/2 = [(m+n√5)/2]5= (m5 + 5m4n√5 + 50m3n2 + 50m2n3√5 + 125mn4 + 25n5√5)/25
(2) So, m' = (m5 + 50m3n2 + 125mn4)/24
(3) This means that 16m' ≡ m5 (mod 5)
(4) So, n' = (5m4n + 50m2n3 + 25n5)/24
(5) This means that 16n' ≡ 0 (mod 5) and 5 divides n'.
(6) a + b√5 = [(m' + n'√5)/2][(t + u√5)/2] = (m't + m'u√5 + n't√5 + 5n'u)/4
(7) So:
4a = m't + 5n'u
4b = m'u + n't
(8) From this we can conclude that 5 doesn't divide m' (otherwise from #7, 5 would divide a which it does not)
(9) We can also conclude that 5 doesn't divide m (otherwise from #3, 5 woud divide m' which from #8 it does not)
(10) From #7, we know that 5 divides u (since it divides 4b, n't but doesn't divide m')
(11) We also know that t = ± 2 since u = 0 and (t + u√5)/2 is a unit.
(12) From #11, we know that a + b√5 = ± [(m + n√5)/2]5
(13) From #12 and Lemma 1 above and the fact that m ≡ n (mod 2), we can conclude that m,n are even.
(14) Let:
c = ±m/2
d = ±n/2
(15) a + b√5 = ±(c + d√5)5 = c5 + 5c4d√5 + 50c3d2 + 50c2d3√5 + 125cd4 + 25d5√5.
(16) So:
a = c5 + 50c3c2 + 125cd4 = c(c4 + 50c2d2 + 125d4)
b = 5c4d + 50c2d3 + 25d5 = 5d(c4 + 10c2d2 + 5d4)
(17) gcd(c,d) = 1 since c divides a, d divides b. If gcd(c,d) ≠ 1 then it would mean a,b have a common factor which they don't.
(18) c,d have different parities
(a) c,d cannot both be even since gcd(c,d)=1 from #17
(b) c,d cannot both be odd since from #16:
a = odd(odd + even + odd) = odd(even) = even
b = odd(odd + even + odd) = odd(even) = even
Which is impossible since a,b have different parities.
(c) Therefore c,d have different parities too.
(19) 5 doesn't divide c since 5 doesn't divide m from #9.
(20) Finally, we know that c,d are nonzero since:
(a) c is nonzero from #16 since a is nonzero
(b) d is nonzero from #16 since b is nonzero
QED
Lemma 3: Given a,b such that:
(a) gcd(a,b)=1
(b) a,b have different parities (one is odd, one is even)
(c) a,b are nonzero
(d) 5 doesn't divide a
(e) 5 divides b
(f) a + b√5 = [(m + n√5)/2]5([t+u√5]/2) where u ≠ 0.
Then:
(a) a = c(c4 + 50c2d2 + 125d4)
(b) b = 5d(c4 + 10c2d2 + 5d4)
(c) gcd(c,d)=1
(d) c,d have different parities
(e) 5 doesn't divide c
(f) c,d are nonzero
Proof:
(1) Since [t+u√5]/2 is a unit, we know that there exists an integer e (see here) such that:
[t+u√5]/2 = ±([1 + √5]/2)e
(2) By our assumption that u ≠ 0, we know that e ≠ 0
(3) We can assume that e is positive, since we make e positive by replacing [1 + √5]/2 with its inverse -(1 - √5)/2 since:
(a) [(1 + √5)/2]-1 = 2/(1 + √5) = 2(1 - √5)/(1 - 5) = (2 - 2√5)/(-4) = (1 - √5)/(-2) = -(1 - √5)/2
(b) [(1 + √5)/2]-e = ([(1 + √5)/2]-1)e = [-(1 - √5)/2 ]e
(4) We know that e is ≥ 2 since:
(a) Since 5 divides b, it must divide u (see the reasoning in lemma 2)
(b) But if e = 1, then u = ±1 which is not divisible by 5.
(5) So, we can assume that (t + u√5)/2 = [±(1 √5)e]/(2e)
(6) Which implies that:
±(2e-1)(t + u√5) = (1 ± √5)e
(7) Using the binomial theorem (see here), we see that 2e-1u ≡ ±e (mod 5) since:
(1 ± √5)e = 1 + e√5 + [e*(e-1)]5 + [e*(e-1)(e-2)](5)√5 + ... + (√5)e
Since e ≥ 2, we know that all other value but the second one are divisible by 5.
(8) Since 5 divides u (from #4a), we know that e ≡ 0 (mod 5) so that 5 divides e.
(9) Then there must exist f such that e = 5f.
(10) We can assume that there exist c',d' such that:
(c' + d'√5)/2 = [(m + n√5)/2][(1 ± √5)/2]f
(11) From this we know that:
a + b√5 = [(c' + d'√5)/2]
(12) We further know that c', d' have the same parity (because of the nature of Z[(1 + √5)/2]) so that we can assume that they are even from Lemma 1 above.
(13) This allows us to suppose there c,d such that:
c = ±c'/2, d = ±d'/2
(14) We now have the equation:
a + b√5 = ±(c + d√5)5
(15) This allows to follow the same logic from Lemma 2, starting at step #15.
QED
Saturday, January 14, 2006
Discriminants and Reduced Equations
In today's blog, I will go over some lemmas that are needed to complete the solution to Pell's Equation using purely periodic continued fractions.
The lemmas in today's proof is taken from Heinrich Dorrie's 100 Great Problems of Elementary Mathematics.
Lemma 1: Let D = 4n and let g = floor(√n). The coefficients for a reduced quadratic equation are: a = 1, b = -2g, c = g2 - n.
(1) The discriminant D = b2 - 4ac (see here for review)
(2) We know that r + b is less than 2a which is less than r - b since:
(a) 2√n - 2g is less than 2 [since we defined g as the floor of √n, we know that this value - g is less than 1.
(b) We also know that 2 is less than 2√n + 2g since √n + g is greater than 1.
(c) Since r = 2√n and since we are assuming that b = -2g, r + b = 2√n - 2g and likewise r - b = 2√n + 2g
(3) This proves tht we have a reduced fraction since:
-(r + b)/2a is a negative proper fraction
r - b/2a is a positive improper fraction.
QED
Lemma 2: Let D = 4n + 1. Let g be the largest integer for which g2 + g will be smaller than n [so that, (g + 1)2 + (g+1) is greater than n]. In this case, setting a = 1, b = -(2g + 1), c = g2 + g - n gives us a reduced quadratic equation.
(1) First, we note that √D - (2g + 1) is less than 2.
(a) From our assumption about g2 + g, we know that (g + 1)2 + (g+1) is greater than n and that:
(g+1)2 + g + 1 = g2 + 2g + 1 + g + 1 = g2 + 3g + 2
(b) Multiplying the above by 4 and adding 1 to each side gives us:
4g2 + 12g + 9 is greater than 4n + 1.
(c) So that we have:
(2g + 3)2 is greater than D.
(d) From this, it follows that 2g + 3 is greater than √D
(e) Rearranging this gives us:
√D - (2g + 1) is less than 2.
(2) 2 is less than √D + 2g + 1 since:
D ≥ 1 and g≥ 1.
(3) We then have r + b is less than 2a since:
r = √D and b = -(2g + 1)
(4) We also have 2a is less than r - b.
(5) So using the same reasoning in Lemma 1 we are done.
QED
The lemmas in today's proof is taken from Heinrich Dorrie's 100 Great Problems of Elementary Mathematics.
Lemma 1: Let D = 4n and let g = floor(√n). The coefficients for a reduced quadratic equation are: a = 1, b = -2g, c = g2 - n.
(1) The discriminant D = b2 - 4ac (see here for review)
(2) We know that r + b is less than 2a which is less than r - b since:
(a) 2√n - 2g is less than 2 [since we defined g as the floor of √n, we know that this value - g is less than 1.
(b) We also know that 2 is less than 2√n + 2g since √n + g is greater than 1.
(c) Since r = 2√n and since we are assuming that b = -2g, r + b = 2√n - 2g and likewise r - b = 2√n + 2g
(3) This proves tht we have a reduced fraction since:
-(r + b)/2a is a negative proper fraction
r - b/2a is a positive improper fraction.
QED
Lemma 2: Let D = 4n + 1. Let g be the largest integer for which g2 + g will be smaller than n [so that, (g + 1)2 + (g+1) is greater than n]. In this case, setting a = 1, b = -(2g + 1), c = g2 + g - n gives us a reduced quadratic equation.
(1) First, we note that √D - (2g + 1) is less than 2.
(a) From our assumption about g2 + g, we know that (g + 1)2 + (g+1) is greater than n and that:
(g+1)2 + g + 1 = g2 + 2g + 1 + g + 1 = g2 + 3g + 2
(b) Multiplying the above by 4 and adding 1 to each side gives us:
4g2 + 12g + 9 is greater than 4n + 1.
(c) So that we have:
(2g + 3)2 is greater than D.
(d) From this, it follows that 2g + 3 is greater than √D
(e) Rearranging this gives us:
√D - (2g + 1) is less than 2.
(2) 2 is less than √D + 2g + 1 since:
D ≥ 1 and g≥ 1.
(3) We then have r + b is less than 2a since:
r = √D and b = -(2g + 1)
(4) We also have 2a is less than r - b.
(5) So using the same reasoning in Lemma 1 we are done.
QED
Subscribe to:
Posts (Atom)
