In today's blog, I will continue the proof for Fermat's Last Theorem n=7.
The details for today are based on Paulo Ribenboim's Fermat's Last Theorem for Amateurs.
Lemma 1: Given u2 = s4 + 6t2s2 - t4/7 where s,t are integers and gcd(s,t)=1, we can conclude that there exists an integer v such that:
(a) t = 7ev
(b) 7 doesn't divide v
(c) gcd(s2 + 3*72ev2 + u,s2 + 3*72ev2 - u) is a power of 2 or 1.
Proof:
(1) s,t are integers so 7s4 + 42t2s2 - t4 is an integer.
(2) But this means that 7u2 is an integer which means that u2 is an integer. If u2 were not an integer then it u = would have to equal some number of √7 which is impossible since u is a rational number and √7 is not (see here for details).
(3) But from (a), we also note that 7 must divide t4 which means from Euclid's Generalized Lemma, 7 must divide t.
(4) If e is the number of times that 7 divides t, then there exists v such that:
t = 7ev and 7 doesn't divide v.
(5) Inserting this into the value of u2 gives us:
u2 = s4 + 6*(72e)v2s2 - 74e-1v4 = (s2 + 3*72ev2)2 - 64*74e-1v4
(6) Subtracting u2 from both sides and adding 64*74e-1v4 to both sides gives us:
(s2 + 3*72ev2)2 - u2 = (s2 + 3*72ev2 + u)(s2 + 3*72ev2 - u) = 64*74e-1v4
(7) Now, we can show that gcd( s2 + 3*72ev2 + u , s2 + 3*72ev2 - u) = 2f since:
(a) Assume that a prime p divides both and it is not 2.
(b) Then p divides u [since 2u = s2 + 3*72ev2 + u -( s2 + 3*72ev2 - u) and p doesn't divide 2.]
(c) We also know that p divides s2 + 3*72ev2 [since 2(s2 + 3*72ev2) = s2 + 3*72ev2 + u + (s2 + 3*72ev2 - u) and p doesn't divide 2]
(d) We know that p ≠ 7 since then 7 would divide s but this is impossible since 7 divides t and gcd(s,t)=1.
(e) We know from #6, that p divides 64*74e-1v4
(f) This means that p must divide v (since we are assuming it is not 2 and we know it is not 7)
(g) Going back to (c), it must also divide s.
(h) But this is impossible since it would then also divide t (since t = 7ev) and we know that gcd(s,t)=1.
(i) So we have a contradiction and we reject our assumption (7a).
QED
Saturday, January 21, 2006
Fermat's Last Theorem: Proof for n=7: Existence of u
In today's blog, I will continue the proof for Fermat's Last Theorem n=7.
The details for today are based on Paulo Ribenboim's Fermat's Last Theorem for Amateurs.
Lemma 1: if ax2 + bx + c = 0 where a,b,c are rational numbers and x is a rational number, then b2 - 4ac is the square of a rational number.
(1) We know that x = (-b ±√b2 - 4ac)/2 from the quadratic equation formula (see here).
(2) We know that 2ax is rational since 2 is an integer and a,x are rational.
(3) Let d = √b2 - 4ac
(4) From #1 and #2, we know that -b ± d must also be rational since it is equal to 2ax.
(5) Then d must be rational since:
d = ±(2ax + b) where 2ax is a rational and b is an integer.
QED
Lemma 2: if Q = (t + s)/2t, then ([1 - Q + Q2]/2)2 = ([3t2 + s2]/8t2)2
Proof:
(1) (1 - Q + Q2)/2 = (1 - [(t + s)/2t] + [(t + s)/2t]2)/2 =
= [3t2 + 5s2]/8t2
(2) From this the conclusion follows.
QED
Lemma 3: Given M,Q are rational numbers, M2 - M(1 - Q + Q2) + 1/7 = 0, then there exists a rational number u such that:
u2 = s4 + 6t2s2 - t4/7
s,t are integers
s/t = 2Q-1
gcd(s,t) = 1
t is greater than 0
Proof:
(1) Since M, Q are rational and M2 - M(1 - Q + Q2) + 1/7 = 0, using lemma 1 above, we can conclude that:
[(1 - Q + Q2)/2]2 - 1/7 is the square of a rational number.
(2) Let s/t = 2Q - 1
(a) Since Q is a rational number, we know that there exists s',t' such that Q = s'/t'
(b) 2Q - 1 is therefore also a rational number since:
2Q - 1 = (2s' - t')/t'
(3) We can assume gcd(s,t)=1 since if there were any common divisors, we could divide them out an s/t would still = 2Q - 1.
(4) We know that t ≠ 0 and we can assume that it is positive since we can multiply -1 to s and still have s/t = 2Q-1.
(5) Q = (t + s)/2t since:
2Q = s/t + 1 = (s + t)/t
Q = (s + t)/2t
(6) Using Lemma 2, we note that:
(1 - Q + Q2)2 - 4/7 = 4[(1 - Q + Q2)2 - 1/7] = 4[(3t2 + s2)2/(8t2)2 - 1/7]
(7) Applying #1 with #6, we can conclude that:
(3t2 + s2)2/(8t2)2 - 1/7 is the square of a rational number.
(8) Let u2 = 64t4[(3t2 + s2)2/(8t2)2 - 1/7]
(9) Since 64t4 is the square of a rational number and using #7, we can conclude that u2 is the square of a rational number which means that u is a rational number.
(10) Further, we note that:
64t4[(3t2 + s2)2/(8t2)2 - 1/7] = s4 + 6t2s2 - t4/7.
QED
The details for today are based on Paulo Ribenboim's Fermat's Last Theorem for Amateurs.
Lemma 1: if ax2 + bx + c = 0 where a,b,c are rational numbers and x is a rational number, then b2 - 4ac is the square of a rational number.
(1) We know that x = (-b ±√b2 - 4ac)/2 from the quadratic equation formula (see here).
(2) We know that 2ax is rational since 2 is an integer and a,x are rational.
(3) Let d = √b2 - 4ac
(4) From #1 and #2, we know that -b ± d must also be rational since it is equal to 2ax.
(5) Then d must be rational since:
d = ±(2ax + b) where 2ax is a rational and b is an integer.
QED
Lemma 2: if Q = (t + s)/2t, then ([1 - Q + Q2]/2)2 = ([3t2 + s2]/8t2)2
Proof:
(1) (1 - Q + Q2)/2 = (1 - [(t + s)/2t] + [(t + s)/2t]2)/2 =
= [3t2 + 5s2]/8t2
(2) From this the conclusion follows.
QED
Lemma 3: Given M,Q are rational numbers, M2 - M(1 - Q + Q2) + 1/7 = 0, then there exists a rational number u such that:
u2 = s4 + 6t2s2 - t4/7
s,t are integers
s/t = 2Q-1
gcd(s,t) = 1
t is greater than 0
Proof:
(1) Since M, Q are rational and M2 - M(1 - Q + Q2) + 1/7 = 0, using lemma 1 above, we can conclude that:
[(1 - Q + Q2)/2]2 - 1/7 is the square of a rational number.
(2) Let s/t = 2Q - 1
(a) Since Q is a rational number, we know that there exists s',t' such that Q = s'/t'
(b) 2Q - 1 is therefore also a rational number since:
2Q - 1 = (2s' - t')/t'
(3) We can assume gcd(s,t)=1 since if there were any common divisors, we could divide them out an s/t would still = 2Q - 1.
(4) We know that t ≠ 0 and we can assume that it is positive since we can multiply -1 to s and still have s/t = 2Q-1.
(5) Q = (t + s)/2t since:
2Q = s/t + 1 = (s + t)/t
Q = (s + t)/2t
(6) Using Lemma 2, we note that:
(1 - Q + Q2)2 - 4/7 = 4[(1 - Q + Q2)2 - 1/7] = 4[(3t2 + s2)2/(8t2)2 - 1/7]
(7) Applying #1 with #6, we can conclude that:
(3t2 + s2)2/(8t2)2 - 1/7 is the square of a rational number.
(8) Let u2 = 64t4[(3t2 + s2)2/(8t2)2 - 1/7]
(9) Since 64t4 is the square of a rational number and using #7, we can conclude that u2 is the square of a rational number which means that u is a rational number.
(10) Further, we note that:
64t4[(3t2 + s2)2/(8t2)2 - 1/7] = s4 + 6t2s2 - t4/7.
QED
Thursday, January 19, 2006
Fermat's Last Theorem: Proof for n=7: Newton's Formula
In today's blog, I will continue the proof for Fermat's Last Theorem n=7.
The details for today are based on Paulo Ribenboim's Fermat's Last Theorem for Amateurs.
Today's proof uses a method that was first used by Sir Isaac Newton.
Lemma 1: Newton's Method:
(a) Let p = x + y + z
(b) Let q = xy + xz + yz
(c) Let r = xyz
(d) Let S1 = p
(e) Let S2 = p2 - 2q
(f) Let S3 = p3 - 3pq +3r
Then
For n ≥ 4 Sn = Sn-1p - Sn-2q + Sn-3r is a recurrence relationship where Sn = xn + yn + zn.
Proof:
(1) We start by noting that this result works for S1, S2, and S3:
S1 = p = x + y + z = x1 + y1 + z1
S2 = p2 - 2q = (x + y + z)2 - 2(xy + xz + yz) =
x2 + xy + xz + y2 + xy + yz + z2 + xz + yz - 2xy -2xz - 2yz = x2 + y2 + z2
S3 = p3 - 3pq + 3r = (x + y + z)3 - 3(x + y + z)(xy + xz + yz) + 3(xyz) = x3 + y3 + x3
(2) Let's expand S4:
S4 = S3p - S2q + S1r =
= (x3 + y3 + z3)(x + y + z) - (x2 + y2 + z2)(xy + yz + xz) + (x + y + z)(xyz)
(x3 + y3 + z3)(x + y + z) =
= x4 + y4 + z4 + x3y + x3z + xy3 + y3z + xz3 + yz3
(x2 + y2 + z2)(xy + xz + yz) =
= x3y + x3z + x2yz + xy2 + xy2z + y3z + xyz2 + xz3 + yz3
(x + y + z)(xyz) = x2yz + xy2z +xyz2
Combining all the above gives us:
S4 = x4 + y4 + z4
(3) Since it's true for S4, we know that there exists some n ≥ 4 such that the Sn recurrence formula works for all values between 1 and n.
(4) Sn+1 = Snp - Sn-1q + Sn-2r =
(xn + yn + zn)(x + y + z) - (xn-1 + yn-1 + zn-1)(xy + xz + yz) + (xn-2 + yn-2 + zn-2)(xyz)
(xn + yn + zn)(x + y + z) =
= xn+1 + yn+1 + zn+1 + xny + xnz + xyn + ynz + xzn + yzn
(xn-1 + yn-1 + zn-1)(xy + xz + yz) =
= xny + xnz + xn-1yz + xyn + xyn-1z + ynz + xyzn-1 + xzn + yzn
(xn-2 + yn-2 + zn-2)(xyz) =
= xn-1yz + xyn-1z + xyzn-1
Combining all this together gives us:
Sn+1 = xn+1 + yn+1 + zn+1
(5) By the Principle of Induction, we are done.
QED
Lemma 2: If there exists integers x,y,z such that:
(a) x7 + y7 + z7 = 0
(b) x + y + z ≠ 0
(c) xyz ≠ 0
(d) p = x + y + z
(e) q = xy + xz + yz
(f) r = xyz
Then
x7 + y7 + z7 = p7 - 7p5q + 7p4r + 14p3q2 - 21p2qr - 7pq3 + 7pr2 + 7q2r.
Proof:
(1) By Lemma 1 above, we get:
S7 = S6p - S5q + S4r = x7 + y7 + z7
S6 = p6 - 6p4q + 6p3r + 9p2q2 - 12pqr - 2q3 + 3r2
S5 = p5 -5p3q + 5p2r + 5pq2 - 5qr
S4 = p4 - 4p2q + 4pr + 2q2
(2) Combining these all together gives us:
x7 + y7 + z7 = p7 - 7p5q + 7p4r + 14p3q2 - 21p2qr - 7pq3 + 7pr2 + 7q2r.
QED
The details for today are based on Paulo Ribenboim's Fermat's Last Theorem for Amateurs.
Today's proof uses a method that was first used by Sir Isaac Newton.
Lemma 1: Newton's Method:
(a) Let p = x + y + z
(b) Let q = xy + xz + yz
(c) Let r = xyz
(d) Let S1 = p
(e) Let S2 = p2 - 2q
(f) Let S3 = p3 - 3pq +3r
Then
For n ≥ 4 Sn = Sn-1p - Sn-2q + Sn-3r is a recurrence relationship where Sn = xn + yn + zn.
Proof:
(1) We start by noting that this result works for S1, S2, and S3:
S1 = p = x + y + z = x1 + y1 + z1
S2 = p2 - 2q = (x + y + z)2 - 2(xy + xz + yz) =
x2 + xy + xz + y2 + xy + yz + z2 + xz + yz - 2xy -2xz - 2yz = x2 + y2 + z2
S3 = p3 - 3pq + 3r = (x + y + z)3 - 3(x + y + z)(xy + xz + yz) + 3(xyz) = x3 + y3 + x3
(2) Let's expand S4:
S4 = S3p - S2q + S1r =
= (x3 + y3 + z3)(x + y + z) - (x2 + y2 + z2)(xy + yz + xz) + (x + y + z)(xyz)
(x3 + y3 + z3)(x + y + z) =
= x4 + y4 + z4 + x3y + x3z + xy3 + y3z + xz3 + yz3
(x2 + y2 + z2)(xy + xz + yz) =
= x3y + x3z + x2yz + xy2 + xy2z + y3z + xyz2 + xz3 + yz3
(x + y + z)(xyz) = x2yz + xy2z +xyz2
Combining all the above gives us:
S4 = x4 + y4 + z4
(3) Since it's true for S4, we know that there exists some n ≥ 4 such that the Sn recurrence formula works for all values between 1 and n.
(4) Sn+1 = Snp - Sn-1q + Sn-2r =
(xn + yn + zn)(x + y + z) - (xn-1 + yn-1 + zn-1)(xy + xz + yz) + (xn-2 + yn-2 + zn-2)(xyz)
(xn + yn + zn)(x + y + z) =
= xn+1 + yn+1 + zn+1 + xny + xnz + xyn + ynz + xzn + yzn
(xn-1 + yn-1 + zn-1)(xy + xz + yz) =
= xny + xnz + xn-1yz + xyn + xyn-1z + ynz + xyzn-1 + xzn + yzn
(xn-2 + yn-2 + zn-2)(xyz) =
= xn-1yz + xyn-1z + xyzn-1
Combining all this together gives us:
Sn+1 = xn+1 + yn+1 + zn+1
(5) By the Principle of Induction, we are done.
QED
Lemma 2: If there exists integers x,y,z such that:
(a) x7 + y7 + z7 = 0
(b) x + y + z ≠ 0
(c) xyz ≠ 0
(d) p = x + y + z
(e) q = xy + xz + yz
(f) r = xyz
Then
x7 + y7 + z7 = p7 - 7p5q + 7p4r + 14p3q2 - 21p2qr - 7pq3 + 7pr2 + 7q2r.
Proof:
(1) By Lemma 1 above, we get:
S7 = S6p - S5q + S4r = x7 + y7 + z7
S6 = p6 - 6p4q + 6p3r + 9p2q2 - 12pqr - 2q3 + 3r2
S5 = p5 -5p3q + 5p2r + 5pq2 - 5qr
S4 = p4 - 4p2q + 4pr + 2q2
(2) Combining these all together gives us:
x7 + y7 + z7 = p7 - 7p5q + 7p4r + 14p3q2 - 21p2qr - 7pq3 + 7pr2 + 7q2r.
QED
Fermat's Last Theorem: Proof for n=7: Existence M,Q
In today's blog, I will continue the proof for Fermat's Last Theorem n=7.
The details for today are based on Paulo Ribenboim's Fermat's Last Theorem for Amateurs.
Lemma 1: If x,y,z are integers such that:
(a) p = x + y + z ≠ 0
(b) q = xy + xz + yz
(c) r = xyz
Then:
x7 + y7 + z7 = p7 - 7(pq - r)(p4 - p2q + q2) + 7(pq - r)2p.
Proof:
(1) From Newton's Formula for sums, we get
x7 + y7 + z7 = p7 - 7p5q + 7p4r + 14p3q2 - 21p2qr - 7pq3 + 7pr2 + 7q2r.
(2) We know that:
(-7)(pq - r)(p4 - p2q + q2) = -7p5q + 7p3q2 - 7pq3 + 7p4r - 7p2qr + 7q2r.
(3) From the Binomial Theorem, we know that:
(pq - r)2p = 7p3q2 - 14p2qr + 7pr2
(4) Combining #1, #2, and #3 gives us:
p7 - 7(pq -r)(p4 - p2q + q2) + 7(pq -r)2p =
p7 - 7p5q + 7p4r + 14p3q2 - 21p2qr - 7pq3 + 7pr2 + 7q2r.
QED
Lemma 2: If x,y,z are integers such that:
(a) x7 + y7 + z7 = 0
(b) xyz ≠ 0
(c) x + y + z ≠ 0
Then there exist rational numbers M,Q such that:
(a) p = x + y + z
(b) q = xy + xz + yz
(c) r = xyz
(d) m = pq - r
(e) Q = q/p2
(f) M = m/p3
(g) M2 - M(1 - Q + Q2) + 1/7 = 0
Proof:
(1) Let p = x + y + z.
(2) Let q = xy + xz + yz.
(3) Let r = xyz
(4) From Lemma 1 above, we know that:
x7 + y7 + z7 = p7 - 7(pq - r)(p4 - p2q + q2) + 7(pq - r)2p.
(5) Let m = pq - r
(6) #4 gives us:
x7 + y7 + z7 = p7 - 7m(p4 - p2q + q2) + 7m2p.
(7) Let Q = q/p2 so that q = p2Q
(8) Let M = m/p3 so that m = p3M
(9) Then, #6 gives us:
x7 + y7 + z7 = p7-7p3M(p4 - p4Q + p4Q2) + 7p7M2 = p7 - 7p7M - 7p7MQ -7p7MQ2 + 7p7M2
(10) Dividing both sides by 7p7 (since x7 + y7 + z7 = 0) gives us:
1/7 -M -MQ - MQ2 + M2 = M2 - M(1 - Q + Q2) + 1/7 = 0
QED
The details for today are based on Paulo Ribenboim's Fermat's Last Theorem for Amateurs.
Lemma 1: If x,y,z are integers such that:
(a) p = x + y + z ≠ 0
(b) q = xy + xz + yz
(c) r = xyz
Then:
x7 + y7 + z7 = p7 - 7(pq - r)(p4 - p2q + q2) + 7(pq - r)2p.
Proof:
(1) From Newton's Formula for sums, we get
x7 + y7 + z7 = p7 - 7p5q + 7p4r + 14p3q2 - 21p2qr - 7pq3 + 7pr2 + 7q2r.
(2) We know that:
(-7)(pq - r)(p4 - p2q + q2) = -7p5q + 7p3q2 - 7pq3 + 7p4r - 7p2qr + 7q2r.
(3) From the Binomial Theorem, we know that:
(pq - r)2p = 7p3q2 - 14p2qr + 7pr2
(4) Combining #1, #2, and #3 gives us:
p7 - 7(pq -r)(p4 - p2q + q2) + 7(pq -r)2p =
p7 - 7p5q + 7p4r + 14p3q2 - 21p2qr - 7pq3 + 7pr2 + 7q2r.
QED
Lemma 2: If x,y,z are integers such that:
(a) x7 + y7 + z7 = 0
(b) xyz ≠ 0
(c) x + y + z ≠ 0
Then there exist rational numbers M,Q such that:
(a) p = x + y + z
(b) q = xy + xz + yz
(c) r = xyz
(d) m = pq - r
(e) Q = q/p2
(f) M = m/p3
(g) M2 - M(1 - Q + Q2) + 1/7 = 0
Proof:
(1) Let p = x + y + z.
(2) Let q = xy + xz + yz.
(3) Let r = xyz
(4) From Lemma 1 above, we know that:
x7 + y7 + z7 = p7 - 7(pq - r)(p4 - p2q + q2) + 7(pq - r)2p.
(5) Let m = pq - r
(6) #4 gives us:
x7 + y7 + z7 = p7 - 7m(p4 - p2q + q2) + 7m2p.
(7) Let Q = q/p2 so that q = p2Q
(8) Let M = m/p3 so that m = p3M
(9) Then, #6 gives us:
x7 + y7 + z7 = p7-7p3M(p4 - p4Q + p4Q2) + 7p7M2 = p7 - 7p7M - 7p7MQ -7p7MQ2 + 7p7M2
(10) Dividing both sides by 7p7 (since x7 + y7 + z7 = 0) gives us:
1/7 -M -MQ - MQ2 + M2 = M2 - M(1 - Q + Q2) + 1/7 = 0
QED
Fermat's Last Theorem: Proof for n=7: x + y + z ≠ 0
In today's blog, I will continue the proof for Fermat's Last Theorem n=7. Today's proof is used in step 3 of FLT n=7 proof.
The details for today are based on Paulo Ribenboim's Fermat's Last Theorem for Amateurs.
Lemma 1: x7 + y7 + z7 = 0, x,y,z integers, then x+y+z=0
(1) Assume that x+y+z ≠ 0
(2) We know that there exists Q,M (see here) such that:
p = x + y + z
q = xy + xz + yz
r = xyz
m = pq - r
Q = q/p2
M = m/p3
M2 - M(1 - Q + Q2) + 1/7 = 0
(3) We can then conclude that there exists u (see here) such that:
u2 = s4 + 6t2s2 - t4/7
u is a rational number
s/t = 2Q-1
gcd(s,t) = 1
t is greater than 0
(4) We can also conclude that there exists an integer v (see here) such that:
t = 7ev
7 does not divide v
gcd(s2 + 3 * 72ev2 + u, s2 + 3 * 72ev2 - u) is a power of 2 or it is 1.
(5) But v is neither odd (see here) nor even (see here) so we have a contradiction.
QED
The details for today are based on Paulo Ribenboim's Fermat's Last Theorem for Amateurs.
Lemma 1: x7 + y7 + z7 = 0, x,y,z integers, then x+y+z=0
(1) Assume that x+y+z ≠ 0
(2) We know that there exists Q,M (see here) such that:
p = x + y + z
q = xy + xz + yz
r = xyz
m = pq - r
Q = q/p2
M = m/p3
M2 - M(1 - Q + Q2) + 1/7 = 0
(3) We can then conclude that there exists u (see here) such that:
u2 = s4 + 6t2s2 - t4/7
u is a rational number
s/t = 2Q-1
gcd(s,t) = 1
t is greater than 0
(4) We can also conclude that there exists an integer v (see here) such that:
t = 7ev
7 does not divide v
gcd(s2 + 3 * 72ev2 + u, s2 + 3 * 72ev2 - u) is a power of 2 or it is 1.
(5) But v is neither odd (see here) nor even (see here) so we have a contradiction.
QED
Wednesday, January 18, 2006
Fermat's Last Theorem: Proof for n = 7: x + y + z = 0
In today's blog, I will continue the proof for Fermat's Last Theorem n=7. Today's proof is used in step four of the FLT n=7 proof.
The details for today are based on Paulo Ribenboim's Fermat's Last Theorem for Amateurs.
Lemma 1: (x + y)7 - x7 - y7 = 7xy(x+y)(x2 + xy + y2)2
(1) With help from the binomial theorem, we get:
(x + y)7 - x7 - y7 = 7x6y + 21x5y2 + 35x4y3 + 35x3y4 + 21x2y5 + 7xy6
(2) (x2 + xy + y2)2 = x4 + 2x3y + 3x2y2 + 2xy3 + y4
(3) (x + y)(x2 + xy + y2)2 =
x5 + 3x4y + 5x3y2 + 5x2y2 + 3xy4 + y5
(4) 7xy(x + y)(x2 + xy + y2)2 =
7x6y + 21x5y2 + 35x4y3 + 35x3y4 + 7xy6
QED
Lemma 2: if ζ =(-1 + √-3)/2, then ζ2 = (-1 - √-3)/2
[(-1 + √-3)/2][(-1 + √-3)/2] = (1 - 2√-3 + -3)/4 = (-2 - 2√-3) /4 = (-1 -√-3)/2
QED
Lemma 3: if x7 + y7 + z7 = 0, x,y,z integers, xyz ≠ 0 and x + y + z = 0, then x,y,z are proportional to 1, ζ, ζ2 where ζ = (-1 + √-3)/2
(1) x + y + z = 0 → z = -x -y = -(x + y)
(2) x7 + y7 + z7 = 0 → z7 = -(x7 + y7)
(3) (x + y)7 - x7 - y7 = (-z)7 + z7 = 0
(4) Applying Lemma 1 above, we get:
7xy(x + y)(x2 + xy + y2)2 = (x + y)7 - x7 - y7 = 0
(5) Since xyz ≠ 0, we know that x ≠ 0 and y ≠ 0 and z ≠ 0.
(6) Since z = -(x + y) and z ≠ 0 we know that x + y ≠ 0.
(7) Therefore x2 + xy + y2 = 0.
(8) But then dividing all sides by x2 gives us:
1 + y/x + (y/x)2 = 0
(9) Using the quadratic equation (see here), we get:
y/x = (-1 ± √1 - 4(1)(1))/2 = (-1 ± √-3)/2
(10) This means that y/x = ζ or y/x = ζ2
(11) Which means that y is proportional to ζ or ζ2
(12) z = -(x + y) = -x(1 + y/x)
So that z = -x(1 + ζ) or z=-x(1 + ζ2)
(13) But 1 + ζ = 1 + (-1 + √-3)/2= (2 - 1 +√-3)/2 = (1 + √-3)/2
So that:
(-x)(1 + ζ) = (-x)[(1 + √-3)/2 ] = x[(-1 - √-3)/2 ] = xζ2
(14) And 1 + ζ2 = 1 + (-1 -√-3)/2 = (2-1 -√-3)/2 = (1 - √-3)/2
So that:
(-x)(1 + ζ2) = (-x)[(1 - √-3)/2] = x[(-1 + √-3)/2] = xζ
(15) This proves that z is proportional to ζ or ζ2
(16) Finally x/y = 1/ζ or x/y=1/ζ2
(a) 1/ζ = 2/(-1 + √-3) = 2(-1 - √-3)/[1 - (-3)] = (-2 - 2√-3)/4 = (-1 - √-3)/2 = ζ2
(b) 1/ζ2 = 2/(-1 -√-3) = 2(-1 + √-3)/[1 - (-3)] = (-2 + 2√-3)/4 = (-1 + √-3)/2 = 1/ζ
(17) So, we see that x too is proportional to either ζ or ζ2
QED
The details for today are based on Paulo Ribenboim's Fermat's Last Theorem for Amateurs.
Lemma 1: (x + y)7 - x7 - y7 = 7xy(x+y)(x2 + xy + y2)2
(1) With help from the binomial theorem, we get:
(x + y)7 - x7 - y7 = 7x6y + 21x5y2 + 35x4y3 + 35x3y4 + 21x2y5 + 7xy6
(2) (x2 + xy + y2)2 = x4 + 2x3y + 3x2y2 + 2xy3 + y4
(3) (x + y)(x2 + xy + y2)2 =
x5 + 3x4y + 5x3y2 + 5x2y2 + 3xy4 + y5
(4) 7xy(x + y)(x2 + xy + y2)2 =
7x6y + 21x5y2 + 35x4y3 + 35x3y4 + 7xy6
QED
Lemma 2: if ζ =(-1 + √-3)/2, then ζ2 = (-1 - √-3)/2
[(-1 + √-3)/2][(-1 + √-3)/2] = (1 - 2√-3 + -3)/4 = (-2 - 2√-3) /4 = (-1 -√-3)/2
QED
Lemma 3: if x7 + y7 + z7 = 0, x,y,z integers, xyz ≠ 0 and x + y + z = 0, then x,y,z are proportional to 1, ζ, ζ2 where ζ = (-1 + √-3)/2
(1) x + y + z = 0 → z = -x -y = -(x + y)
(2) x7 + y7 + z7 = 0 → z7 = -(x7 + y7)
(3) (x + y)7 - x7 - y7 = (-z)7 + z7 = 0
(4) Applying Lemma 1 above, we get:
7xy(x + y)(x2 + xy + y2)2 = (x + y)7 - x7 - y7 = 0
(5) Since xyz ≠ 0, we know that x ≠ 0 and y ≠ 0 and z ≠ 0.
(6) Since z = -(x + y) and z ≠ 0 we know that x + y ≠ 0.
(7) Therefore x2 + xy + y2 = 0.
(8) But then dividing all sides by x2 gives us:
1 + y/x + (y/x)2 = 0
(9) Using the quadratic equation (see here), we get:
y/x = (-1 ± √1 - 4(1)(1))/2 = (-1 ± √-3)/2
(10) This means that y/x = ζ or y/x = ζ2
(11) Which means that y is proportional to ζ or ζ2
(12) z = -(x + y) = -x(1 + y/x)
So that z = -x(1 + ζ) or z=-x(1 + ζ2)
(13) But 1 + ζ = 1 + (-1 + √-3)/2= (2 - 1 +√-3)/2 = (1 + √-3)/2
So that:
(-x)(1 + ζ) = (-x)[(1 + √-3)/2 ] = x[(-1 - √-3)/2 ] = xζ2
(14) And 1 + ζ2 = 1 + (-1 -√-3)/2 = (2-1 -√-3)/2 = (1 - √-3)/2
So that:
(-x)(1 + ζ2) = (-x)[(1 - √-3)/2] = x[(-1 + √-3)/2] = xζ
(15) This proves that z is proportional to ζ or ζ2
(16) Finally x/y = 1/ζ or x/y=1/ζ2
(a) 1/ζ = 2/(-1 + √-3) = 2(-1 - √-3)/[1 - (-3)] = (-2 - 2√-3)/4 = (-1 - √-3)/2 = ζ2
(b) 1/ζ2 = 2/(-1 -√-3) = 2(-1 + √-3)/[1 - (-3)] = (-2 + 2√-3)/4 = (-1 + √-3)/2 = 1/ζ
(17) So, we see that x too is proportional to either ζ or ζ2
QED
Fermat's Last Theorem: Proof for n=7
The proof for Fermat's Last Theorem n=5 came in 1825 thanks to Johann Dirichlet and Adrien-Marie Legendre. It would take 14 years before the proof for n=7 was offered by Gabriel Lamé. It is complicated and uses methods which do not seem generalizeable. This would be the last major proof for Fermat's Last Theorem before Ernst Kummer's breakthrough.
Today's blog is based on the proof offered in Paulo Ribenboim's book Fermat's Last Theorem for Amateurs.
Theorem: if x,y,z are integers, then x7 + y7 = z7 → xyz = 0.
(1) Let ζ = (-1 + √-3)/2
(2) Assume that xyz ≠ 0
(3) xyz ≠ 0 → x + y + z = 0 [ See here for proof ]
(4) x + y + z = 0 → x,y,z are proportional to ζ or ζ2 [ See here for proof ]
(5) But if x,y,z are proportional to ζ or ζ2, then they cannot be integers since:
(a) Let y = xζ where ζ is irrational and x is an integer.
(b) Assume that y is an integer.
(c) Then ζ = y/x where both y,x are integers.
(d) But then ζ by definition is rational which is a contradiction since we know that it is irrational. Therefore, we must reject (b).
(6) So we have a contradiction and we reject #2.
QED
Today's blog is based on the proof offered in Paulo Ribenboim's book Fermat's Last Theorem for Amateurs.
Theorem: if x,y,z are integers, then x7 + y7 = z7 → xyz = 0.
(1) Let ζ = (-1 + √-3)/2
(2) Assume that xyz ≠ 0
(3) xyz ≠ 0 → x + y + z = 0 [ See here for proof ]
(4) x + y + z = 0 → x,y,z are proportional to ζ or ζ2 [ See here for proof ]
(5) But if x,y,z are proportional to ζ or ζ2, then they cannot be integers since:
(a) Let y = xζ where ζ is irrational and x is an integer.
(b) Assume that y is an integer.
(c) Then ζ = y/x where both y,x are integers.
(d) But then ζ by definition is rational which is a contradiction since we know that it is irrational. Therefore, we must reject (b).
(6) So we have a contradiction and we reject #2.
QED
Gabriel Lamé
Gabriel Lamé was born in Tours, France on July 22, 1795. He entered the Ecole Polytechnic in 1813 and while there, published his first mathematical paper in 1816. He graduated Ecole Polytechnic in 1817 and attended the Ecole de Mines from 1817 to 1820.In 1820, Lamé and his colleague Emile Clapeyron were invited to come to Russia to teach mathematics. Lamé was appointed professor at the Institut et Corps du Genie des Voies de Communication located in St. Petersburg. He stayed at this position for 12 years and during this time he lectured and wrote papers on a range of subjects in mathematics, physics, and chemistry. It was while in Russia that he would develop his great interest in railroad development.
Lamé returned to Paris in 1832. That year, he became the Chair of Physics at the Ecole Polytechnique. In 1836, he became the Chief Engineer of Mines. He was also extensively involved in the building of railroads from Paris to Versailles and Paris to St. Germain.
He was elected to the Academie de Sciences in 1843 and that same year, he left Ecole Polytechnique to join Sorbonne where he was a professor of mathematics and probability. He became the chair of mathematical physics and probability at Sorbonne in 1851.
In his lifetime, Lamé worked on a range of very advanced topics including: the stability of vaults, design of suspension bridges, elasticity theory, conduction of heat, general theory of curvilinear coordinates, Fermat's Last Theorem for n=7, differential geometry, and number theory.
Outside of France, he was considered the leading French mathematician of his time by many of his contemporaries such as Carl Friedrich Gauss. Within France, his reputation was less bright. Lamé considered his general theory of curvilinear coordinates to be his most important achievement. Still, this contribution was made obsolete by the discovery of more modern methods.
References
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 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
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
Subscribe to:
Posts (Atom)
