Today's blog continues the discussion on Pell's Equation. Before jumping into the solution to Pell's Equation, it is necessary to review some fundamental properties of Continued Fractions. I will later show how these properties of continued fractions can be used to solve Pell's Equation. For those who are not familiar with Continued Fractions, start here.
One of the most important ideas in dealing with Continued Fractions is the Continued Fraction Approximation Algorithm. This is an algorithm that can be used to convert a real number into a series of integers which make up the continued fraction.
The algorithm itself is made up of two equations which I will label pn and qn. Later, I will show that any finite continued fraction which represents an approximation of a real number is equal to a ratio of these two equations.
All of the ideas presented in today's blog are based on Harold M. Stark's Introduction to Number Theory.
Lemma 1: If [a0, a1, ... an, α] is a continued fraction where all values ai are integers and α is any real number, then there exists series pn and qn where:
[a0, a1, ... an, α ] = (α * pn + pn-1)/(α * qn + qn-1)
(1) Let [a0,a1, ...an, α] be a continued fraction such that:
[a0,a1,...an, α ] = a0 + 1/[a1 + 1/(a2 + ... + 1/α)]
(2) Let pn be a sequence based on a0 ... an such that:
p0 = a0
p1 = a0*a1 + 1
pn+2 = (pn+1)(an+2) + pn
For example, p2 = (p1)(a2) + p0 = (a0a1 + 1)(a2) + a0
(3) Let qn be a sequence based on a0 ... an such that:
q0 = 1
q1 = a1
qn+2 = (qn+1)(an+2) + qn
For example, q2 = (q1)(a2) + q0 = (a1)(a2) + 1
(4) So, consider the case where n = 1, then we have:
[a0, a1, α] = a0 + 1/[(a1 + 1/α)] = a0 + 1/[(a1α + 1)/α] = a0 + α/(a1α + 1) =
[a0(a1α + 1) + α]/(a1α + 1) = [α(a0a1 + 1) + a0]/(a1α + 1)
(5) Now, applying the definition given above for pn and qn gives us:
[a0,a1,α] = (α*p1 + p0)/(α*q1 + q0)
(6) So that, for n=1, we have:
[a0, a1, α] = (α*p1 + p0)/(α*q1 + q0)
(7) Let's assume that this is true up to some value n so that:
[a0, a1, ..., an, α] = (α*pn + pn-1)/(α*qn + qn-1)
(8) Now, we know that: [a0, a1, ..., an, an+1, α] = [a0, a1, ..., an, an+1 + 1/α] by the definition of continued fractions.
(9) So by our assumption in #7:
[a0, a1, ..., an, an+1 + 1/α] = [(an+1 + 1/α)*pn + pn-1]/[(an+1 + 1/α)*qn + qn-1]=
(an+1*pn + pn/α + pn-1)/(an+1*qn + qn/α + qn-1)
(10) Now, multiplying the above by α/α gives us:
(an+1*pn + pn/α + pn-1)/(an+1*qn + qn/α + qn-1) =
=(α*an+1*pn + pn + α*pn-1)/(α*an+1*qn + qn + α*qn-1) =
=[α(an+1pn + pn-1) + pn]/[α(an+1qn + qn-1) + qn]
(11) And finally, applying the series pn and qn gives us:
[α(an+1pn + pn-1) + pn]/[α(an+1qn + qn-1) + qn] = (αpn+1 + pn)/(αqn+1 + qn)
(12) Applying the principle of induction, we are done.
QED
Theorem 1: The Continued Fraction Approximation Algorithm
For any given finite continued fraction [ a0, a1, ... an ] where all ai are integers, using Lemma 1 to compute pn and qn we find that:
[ a0, a1, ... an ] = pn / qn
(1) Let's define pn, qn using the series in Lemma 1.
(2) For case n=1, we have:
[a0, a1] = a0 + 1/a1 = (a0*a1 + 1)/a1 [By definition of Continued Fractions]
= p1/q1 [By definition of pn and qn in Lemma 1]
(3) Assume that this is true up to some value n so that [a0, a1, ... an] = pn/qn
(4) Applying Lemma 1, gives us:
[a0, a1, ..., an, an+1] = [(an+1)pn + pn-1]/(an+1)qn + qn-1 = pn+1/qn+1
(5) By the Principle of Induction, we are done.
QED
Now, consider this interesting lemma:
Lemma 2: pn*qn-1 - pn-1*qn = (-1)n-1
(1) Let's start with the Case: n = 1
pn*qn-1 - pn-1*qn = p1* q0 - p0*q1
From Lemma 1 above,
p0 = a0
p1 = a0*a1 + 1
p2 = p1a2 + p0 = (a0a1 + 1)a2 + a0 = a0a1a2 + a2 + a0
q0 = 1
q1 = a1
q2 = q1a2 + q0 = a1a2 + 1
p1q0 = (a0*a1 + 1)*1 = a0*a1+1
p0*q1 = a0*a1
So:
p1*q0 - p0q1 = a0*a1 + 1 - a0*a1 = 1
(2) So let's assume that this is true up to n-1 so that we can assume:
pn-1*qn-2 - pn-2*qn-1 = (-1)n-2
(3) From Lemma 1, step #2 and step #3, we know that:
pn = pn-1*an + pn-2
and
qn = qn-1*an + qn-2
(4) So,
pn*qn-1 - pn-1*qn = (pn-1*an + pn-2)(qn-1) - (pn-1)(qn-1an + qn-2)
= pn-1*an*qn-1 + pn-2qn-1 - pn-1*an*qn-1 - pn-1qn-2 =
= pn-2qn-1 - pn-1qn-2 =
= (-1)(pn-1qn-2 - pn-2qn-1) =
= (-1)(-1)n-2 [From step #2 above]
= (-1)n-1
(4) By the Principle of Induction we are done.
QED
Lemma 3: If α is a positive real number and α = [a0, a1 ... an-1, αn ], then a0 ≥ 0 and all other ai ≥ 1, and αn ≥ 1.
(1) a0 = floor(α) which clearly ≥ 0.
(2) In case n = 1, α1 = 1/(α - a0).
In this case, a0 is less than α (since we are assuming that αn is a nonzero real number).
So, clearly α1 must also be a positive number greater than 1 (since the difference between α and a0 is less than 1)
(3) In case n=2, a1 = floor(α1) is ≥ 1 by the reasoning in step #2. With α1 ≥ 1 and a1 ≥ 1, we know that α2 = 1/(α1 - a1) must also be a positive number ≥ 1.
(4) Let's assume that this is true up to n-1.
(5) At this point, we have a value αn that is a positive real number ≥ 1.
(6) So, an = floor(αn) which means that an ≥ 1.
(7) Finally, αn+1 = 1/(αn - an) which means that it too will be a positive real number ≥ 1.
(8) By the principle of induction we are done.
QED
Corollary 3.1: If α is a negative real number, and α = [a0, a1 ... an-1, αn ], then a0 ≤ 0 and all other ai ≤ -1, and αn ≤ 1.
(1) The reasoning here is the same as Lemma 3 except that we use a ceiling function instead of a floor function where ceiling (-5.6) = -5. In this case, the ai is higher than the αi value and the subtraction is still a negative number.
(2) In this way, we can use the same reasoning as Lemma 3 and we get the result that the answer is the same as in Lemma 3 except that we multiply -1 to all the ai values and also the αn value.
QED
Lemma 4: For a positive real number, if n is greater than 0, then qn+1 is greater than qn
(1) For case n=1:
q1 = a1
q2 = q1a2 + q0 = a1*a2 + 1
Since a1, a2 are both ≥ 1, we know that:
a1 ≤ a1*a2
And therefore:
a1 is less than a1*a2 + 1
(2) Let's assume that this is true up to n so that qn+1 is greater than qn
(3) So, qn+2 = qn+1*an+2 + qn
(4) We know that q1 = a1 which means that q1 ≥ 1. [From Lemma 3]
(5) So qn is greater than 1 (by our assumption in #2)
(6) We also know that an+2 is ≥ 1 which gives us:
qn+1 ≤ qn+1*an+2
(7) And finally, applying #5
qn+1 is less than qn+1*an+2 + 1 ≤ qn+1*an+2 + qn = qn+2
(8) By the Principle of Induction, we are done.
QED
Corollary 4.1 For a positive real number where n is greater than 0, qn ≥ n.
(1) Let's start with n=1
q1 = a1 which is ≥ 1.
(2) Let's assume that this is true up to n+1 so that qn+1 ≥ n+1.
(3) qn+2 = qn+1an + qn
(4) Now qn+2 is greater than qn+1 which means that:
qn+2 ≥ qn+1 + 1 ≥ n + 1 + 1 ≥ n + 2.
(5) By the Principle of Induction, we are done.
QED
Corollary 4.2: We can also see for all values of n ≥ 2, pn, pn+1 is greater than pn.
(1) We see that this is true for n=2:
p1 = a0a1 + 1.
p2 = p1a2 + a0.
p3 = p2a3 + p1
Since a0 is ≥ 0 (see above), we see that p1 is ≥ 1.
Now a3 is ≥ 1 so p2 * a3 is at least equal to p2 but since p1 is ≥ 1, we know that p3 must be greater.
(2) Now, we assume it is true for all values up to n.
(3) pn+1 = pnan+1 + pn-1
Since p1 ≥ 1, from (1), we know that p3 is ≥ 1 and all values of n greater than 3 is greater than 1.
So, we know that pn+1 is greater than pn by at least pn-1 which is ≥ 1.
(4) We have now proven that pn+1 is greater than pn for all values of n ≥ 2.
QED
Theorem 2: For a positive irrational number, we can use the approximation algorithm to generate an approximation of any degree of accuracy. In other words:
absolute(α - pn/qn) is less than 1/(qnqn+1) which is less than 1/(qn)2 which is ≤ 1/n2
(1) From Lemma 1, we know that:
α = (αn+1pn + pn-1)/(αn+1qn + qn-1)
(2) Subtracting both sides by pn/qn gives us:
α - pn/qn = (αn+1pn + pn-1)/(αn+1qn + qn-1) - pn/qn =
[qn(αn+1pn + pn-1) - pn(αn+1qn + qn-1)]/[qn(αn+1qn + qn-1)] =
= (qnαn+1pn - qnαn+1pn + pn-1qn - pnqn-1)/[qn(αn+1qn +qn-1) ] =
= (pn-1qn - pnqn-1)/[qn(αn+1qn + qn-1)] =
= (-1)n/[qn(αn+1qn + qn-1)]
(3) We know that for positive irrational numbers, an is less than αn which means that:
1/[qn(an+1qn + qn-1)] is greater than 1/[qn(αn+1qn + qn-1)]
Likewise,
-1/[qn(an+1qn + qn-1)] is less than 1/[qn(αn+1qn + qn-1)]
(4) Now, we need to consider two cases to complete the proof:
Case I: n is even
In this case:
α - pn/qn is less than 1/[qn(an+1qn + qn-1)] = 1/(qnqn+1)
We also know that α - pn is greater than 0 which means that it is also greater than -1/(qn)2
Since qn+1 is greater than qn, we also know that:
α - pn/qn is less than 1/(qnqn) = 1/(qn)2
Putting all this together gives us,
absolute(α - pn / qn) is less than 1/(qn)2
Case II: n is odd
In this case:
α - pn/qn is greater than -1/[qn(an+1qn + qn-1)] = -1/(qnqn+1)
We also know that α - pn is less than 0 which means that it is also less than 1/(qn)2
Since qn+1 is greater than qn, we also know that:
α - pn/qn is greater than -1/(qnqn) = -1/(qn)2
Putting all this together gives us,
absolute(α - pn / qn) is less than 1/(qn)2
(5) Now, since q1 ≥ 1 and qn+1 is greater than qn for n ≥ 1, we know that:
qn ≥ n and:
1/(qn)2 is less than 1/n2
QED
Lemma 5: Let Cn = pn/qn, then:
(a) Cn - Cn-1 = [(-1)n-1]/(qnqn-1)
(b) Cn - Cn-2 = [an(-1)n]/(qnqn-2)
(1) pnqn-1 - qnpn-1 = (-1)n-1. [From Lemma 2 above]
(2) Dividing both sides by qnqn-1 gives us (a).
(3) Cn - Cn-2 = pn/qn - pn-2/qn-2 = (pnqn-2 - pn-2qn)/(qnqn-2)
(4) pnqn-2 - pn-2qn = (anpn-1 + pn-2)qn-2 - pn-2(anqn-1 + qn-2) =
= an(pn-1qn-2 - pn-2qn-1) = ak(-1)n-2
(5) Combining #3 and #4 gives us (b).
QED
Corollary 5.1 C1 is greater than C3 is greater than C5 ... and C0 is less than C2 is less than C4 ...
(1) From Lemma 5(b), we know that Cn is less than Cn-2 if n is odd and Cn is greater than Cn-2 if n is even.
QED
Corollary 5.2 Consecutive Cn lie above or below the exact value of the continued fraction.
(1) From Lemma 5, we know that they will alternate. For odd values of n, Cn will be greater than Cn-1 and for even values of n, Cn will be less than Cn-1.
(2) By Theorem 2, we see that each Cn is a value closer to the exact value of the continued fraction.
(3) Finally, from Theorem 2, step #2, we see that α - pn/qn is alternately above and below the main value. If n is even, then α is above and if it is odd, then α is below.
QED
Lemma 6: For any value n ≥ 1, gcd(pn,qn) = 1.
(1) Assume that f divides both pn and qn
(2) By Lemma 2 above, pnqn-1 - pn-1qn = (-1)n-1
(3) So f divides both implies that f divides (-1)n-1
(4) But the only way this is true is if f = 1.
(5) Which proves that the only common factor they can have is 1.
QED
Sunday, November 27, 2005
Friday, November 04, 2005
Pell's Equation
Despite its name, Pell's Equation has nothing to do with the British mathematician John Pell. The problem was wrongly attributed to Pell by Leonard Euler in a very influencial work that Euler wrote when he was still in his 20s. Despite Euler's mistake (apparently, he had meant to cite Viscount William Brouncker), Pell's name stuck. Interestingly, according to Harold M. Edwards, there is a very good chance that Brouncker also wasn't involved with the problem. The work on the British side may have been done by John Wallis who cited Brouncker as an effort to gain favor with the viscount.
It was Pierre de Fermat who brought Europe's math community to focus on this equation in 1657 when he posed the problem as a challenge to the British mathematicians. Fermat was not the first to identify the problem. Diophantus studied one variant of Pell's equation and a famous problem by Archimedes known as the Cattle Problem can be stated in terms of Pell's equation. Great progress in solving Pell's equation were made by Indian mathematicians by Brahmagupta (born in 598 AD) and Bhascara Acharya (born in 1114 AD).
Pell's equation amounts to this:
Find all integer solutions for x,y where Ax2 + 1 = y2.
Interestingly, when this problem got passed on to the English, the part about "integers" was dropped and the British mathematicians quickly found a solution for rational solutions.
Here's the solution in terms of rational values:
Lemma: There are an infinite number of rational solutions to Ax2 + 1 = y2 where x,y are rational numbers.
(1) Let m = y-1, n = x. Then we know that: (y -1)/x = m/n and y-1 = (m/n)x and y = 1 + (m/n)x.
(2) So, Ax2 + 1 = [1 + (m/n)x]2 = 1 + 2(m/n)x + (m2/n2)x2
(3) Multiplying n2 to both sides gives us:
An2x2 + n2 = n2 + 2mnx + m2x2
And:
An2x2 = 2mnx + m2x2
And:
An2x2 - m2x2 = 2mnx
(4) Dividing x from both sides gives us:
An2x - m2x = 2mn = x(An2 - m2)
So that:
x = 2mn/(An2 - m2)
And:
y = 1 + (m/n)x = 1 + (m/n)(2mn/[An2 - m2]) =1 + 2m2/(An2 - m2) = (An2 - m2 + 2m2)/(An2 - m2) = (An2 + m2)/(An2 - m2)
QED
When Fermat saw the solution for rational values, he rejected it explaining that it was ridiculous to think that he would offer a problem as simple as this. He clarified that the problem is only interesting when the solution is for integers.
The British mathematicians at first responded that Fermat's new problem was artificial. They saw little justification for solving the problem specifically for whole numbers when the solution for rational values was valid. Later, an integer solution and a method for finding solutions was put forward without any proof that the method worked in all circumstances. Historically, Lord Brouncker is given credit for the solution.
The verification of the British method would have to wait over 100 years. It was the great mathematician Joseph-Louis Lagrange, using continued fractions, who showed that the British method worked in all circumstances. Go here to see how continued fractions can be used to provide a solution to Pell's equation.
References
It was Pierre de Fermat who brought Europe's math community to focus on this equation in 1657 when he posed the problem as a challenge to the British mathematicians. Fermat was not the first to identify the problem. Diophantus studied one variant of Pell's equation and a famous problem by Archimedes known as the Cattle Problem can be stated in terms of Pell's equation. Great progress in solving Pell's equation were made by Indian mathematicians by Brahmagupta (born in 598 AD) and Bhascara Acharya (born in 1114 AD).
Pell's equation amounts to this:
Find all integer solutions for x,y where Ax2 + 1 = y2.
Interestingly, when this problem got passed on to the English, the part about "integers" was dropped and the British mathematicians quickly found a solution for rational solutions.
Here's the solution in terms of rational values:
Lemma: There are an infinite number of rational solutions to Ax2 + 1 = y2 where x,y are rational numbers.
(1) Let m = y-1, n = x. Then we know that: (y -1)/x = m/n and y-1 = (m/n)x and y = 1 + (m/n)x.
(2) So, Ax2 + 1 = [1 + (m/n)x]2 = 1 + 2(m/n)x + (m2/n2)x2
(3) Multiplying n2 to both sides gives us:
An2x2 + n2 = n2 + 2mnx + m2x2
And:
An2x2 = 2mnx + m2x2
And:
An2x2 - m2x2 = 2mnx
(4) Dividing x from both sides gives us:
An2x - m2x = 2mn = x(An2 - m2)
So that:
x = 2mn/(An2 - m2)
And:
y = 1 + (m/n)x = 1 + (m/n)(2mn/[An2 - m2]) =1 + 2m2/(An2 - m2) = (An2 - m2 + 2m2)/(An2 - m2) = (An2 + m2)/(An2 - m2)
QED
When Fermat saw the solution for rational values, he rejected it explaining that it was ridiculous to think that he would offer a problem as simple as this. He clarified that the problem is only interesting when the solution is for integers.
The British mathematicians at first responded that Fermat's new problem was artificial. They saw little justification for solving the problem specifically for whole numbers when the solution for rational values was valid. Later, an integer solution and a method for finding solutions was put forward without any proof that the method worked in all circumstances. Historically, Lord Brouncker is given credit for the solution.
The verification of the British method would have to wait over 100 years. It was the great mathematician Joseph-Louis Lagrange, using continued fractions, who showed that the British method worked in all circumstances. Go here to see how continued fractions can be used to provide a solution to Pell's equation.
References
- Harold M. Edwards Fermat's Last Theorem
- Pell's Equation, Wikipedia
- Pell's Equation, MacTutor
Thursday, November 03, 2005
Dirichlet Integers
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 just interested in the mathematical details behind the proof, start here.
Today's blog continues on the problem of factoring a2 - 5b2 using quadratic integers of the form Z[(1 + √5)/2]. For those interested in understanding why we are not using Z[√5], please see here.
For purposes of this blog, when I say Dirichlet integers, I mean integers of the form:
Z[(1 + √5)/2]
That is, integers of the form a + b(1 + √5)/2 where a,b are rational integers.
The basic idea behind the use of quadratic integers in a proof is the following:
(i) Quadratic integers are easier to factor than rational integers.
For example, using Z[(1 + √5)/2] we can factor a2 - 5b2 into (a - b√5)(a + b√5).
(ii) As long as a quadratic integer has unique factorization, it is possible to use quadratic integers to prove existence lemmas.
In the case of Fermat's Last Theorem: n=5, we will use Z[(1 + √5)/2] to prove:
If there exist two integers a,b such that:
(a) gcd(a,b)=1
(b) a,b have different parities (one is odd, one is even)
(c) 5 doesn't divide a
(d) 5 divides b
(e) (a2 - 5b2) is a fifth power.
Then there exists two integers c,d such that:
(i) a = c(c4 + 50c2d2 + 125d4)
(ii) b = 5d(c4 + 10c2d2 + 5d4)
(iii) gcd(c,d)=1
(iv) c,d have different parities
(v) 5 doesn't divide c
(vi) c,d are nonzero
Let's review the basics of Z[(1 + √5)/2]:
Definition
From a previous blog, we know that Z[(1 + √5)/2] is defined as:
a + b(1+√5)/2 [Since 5 ≡ 1 (mod 4), see here]
We also note that Dirichlet integers are charaterized by unique factorization. [See here]
Unique Factorization means that when we are reasoning about Dirichlet Integers, we can make use of the Division Algorithm, Euclid's Lemma, the Fundamental Theorem of Arithmetic, and Relatively Prime Divisors of N-Powers.
Norm Function
The norm is a mapping between Dirichlet integers and rational integers. This function is very useful for identifying units, primes, and in general, reasoning about Dirichlet integers. For review of norms and conjugates, please see here.
A norm for a quadratic integer is equal to the quadratic integer multiplied by its conjugate. So, the first step in figuring out the norm is to figure out the conjugate for a given Dirichlet integer.
Let's start with a Dirichlet integer based on integers a,b:
a + b(1+√5)/2
Now, this value is equivalent to:
[(2a + b) + b√5]/2
So, the conjugate would be:
[(2a + b) - b√5]/2
To simplify, we can set a' = (2a + b), b' = b. We note that a',b' will always have the same parity. In other words, they will both be odd or they both will be even.
Using a',b', the norm is:
Norm = (a' + b'√5)/2*(a' - b'√5)/2 = (a'2 - 5b'2)/4
Putting back in (2a+b) for a' and b for b', gives us:
Norm = (a'2 - 5b'2)/4 = [(2a+b)2 - 5(b)2]/4 =
(4a2 + 4ab + b2 - 5b2)/4 =
(4a2 + 4ab - b2)/4 =
a2 + ab - b2
Unit
A unit is any quadratic integer that divides 1. Units are needed in order to establish unique factorization with quadratic integers. You can review the ideas behind units and associates by starting here.
From a previous result, we know that a unit is also any quadratic integers whose norm is ± 1.
This means that we can determine the units for Dirichlet integers by solving the following equation:
(a'2 - 5b'2)/4 = 1
Which is the same as this:
a'2 - 5b'2 = 4
This is a difficult problem. To find the solution, I will now take a short detour to talk about Pell's Equation (another difficult problem posed by Pierre de Fermat). I will then use the solution to Pell's Equation to identify the units for Dirichlet integers.
Of course, we can simplify the problem by considering a'2 - 5b'2 = -4 which is clearly a=1, b =1.
It turns out that all Dirichlet units have the same form:
±[(1 + √5)/2]±n
Lemma 2: All Dirichlet units have the following form: ±[(1 + √5)/2]±n
(1) We know that (1 + √5)/2 is a unit since:
Norm( (1 + √5)/2 ) = [(1 + √5)/2][(1 - √5)/2] = (1 - 5)/4 = -4/4 = -1
Any value that has a norm = ±1 is a unit. [See here for proof]
(2) Assume that there existed a unit α that does not have the above form.
(3) Let ω = (1 + √5)/2
(4) So, we know that there exists some integer n such that:
α is greater than ωn and is less than ωn+1
(5) We know that ωn is a unit and ωn+1 is a unit since Norm(xn) = Norm(x)*Norm(x)*...*Norm(x) = (± 1)(± 1)*...*(± 1)
(6) Since a unit by definition divides 1, we know that ω-(n) is a unit since ωn is a unit.
(7) Likewise, we know that any unit divides any other unit, so we can divide all values by ωn which gives us:
1 is less than α which is less than ω
(8) But there is no such unit that is between 1 and ω
(a) Let's assume that there is was such a unit β
(b) So, there exists two rational integers: x,y such that β = (x + y√5)/2 that is greater than 1 and less than ω
(c) And (x + y√5) is greater than 2 and less than 2*ω which is less than 4.
(d) Now, since β is a unit, we know that Norm(β) = ± 1 = [(x + y√5)/2][(x - y√5)/2]
(e) This means that x = 1 or x = 2 since:
Case I: [(x + y√5)/2][(x - y√5)/2] = 1
Since (x + y√5)/2 is greater than 1, then (x - y√5)/2 is greater than 0 and less than 1.
So, x - y√5 is greater than 0 and less than 2.
So (x + y√5 + x - y√5) is greater than 2 and less than 6.
So 2x is greater than 2 and less than 6
So x = 2.
Case II: [(x + y√5)/2][(x - y√5)/2] = -1
Since (x + y√5)/2 is greater than 1, then (x - y√5)/2 is greater than -1 and less than 0.
So, x - y√5 is greater than -2 and less than 0.
So (x + y√5 + x - y√5) is greater than 0 and less than 4.
So 2x is greater than 0 and less than 4
So x = 1.
(f) But x ≠ 1 since:
(1 + y√5)/2 is greater than 1 so y must be greater than 0 but then (1 + y√5)/2 cannot be less than (1 + √5)/2
(g) And x ≠ 2 since:
(2 + y√5)/2 is greater than 1 so y must be greater than 0.
(2 + y√5)/2 is less than (1 + √5)/2, so y must be less than 1.
But there is no integer between 0 and 1 so we have reached a contradiction.
QED
Primes
Lemma 3: √5 is also a prime in Z[(1 + √5)/2]
(1) exists since = (0 + 2√5)/2
(2) is prime since Norm(√5) = -5 [See Lemma 5 here]
QED
Lemma 4: 2 is a prime in Z[(1 + √5)/2]
See here for proof.
Today's blog continues on the problem of factoring a2 - 5b2 using quadratic integers of the form Z[(1 + √5)/2]. For those interested in understanding why we are not using Z[√5], please see here.
For purposes of this blog, when I say Dirichlet integers, I mean integers of the form:
Z[(1 + √5)/2]
That is, integers of the form a + b(1 + √5)/2 where a,b are rational integers.
The basic idea behind the use of quadratic integers in a proof is the following:
(i) Quadratic integers are easier to factor than rational integers.
For example, using Z[(1 + √5)/2] we can factor a2 - 5b2 into (a - b√5)(a + b√5).
(ii) As long as a quadratic integer has unique factorization, it is possible to use quadratic integers to prove existence lemmas.
In the case of Fermat's Last Theorem: n=5, we will use Z[(1 + √5)/2] to prove:
If there exist two integers a,b such that:
(a) gcd(a,b)=1
(b) a,b have different parities (one is odd, one is even)
(c) 5 doesn't divide a
(d) 5 divides b
(e) (a2 - 5b2) is a fifth power.
Then there exists two integers c,d such that:
(i) a = c(c4 + 50c2d2 + 125d4)
(ii) b = 5d(c4 + 10c2d2 + 5d4)
(iii) gcd(c,d)=1
(iv) c,d have different parities
(v) 5 doesn't divide c
(vi) c,d are nonzero
Let's review the basics of Z[(1 + √5)/2]:
Definition
From a previous blog, we know that Z[(1 + √5)/2] is defined as:
a + b(1+√5)/2 [Since 5 ≡ 1 (mod 4), see here]
We also note that Dirichlet integers are charaterized by unique factorization. [See here]
Unique Factorization means that when we are reasoning about Dirichlet Integers, we can make use of the Division Algorithm, Euclid's Lemma, the Fundamental Theorem of Arithmetic, and Relatively Prime Divisors of N-Powers.
Norm Function
The norm is a mapping between Dirichlet integers and rational integers. This function is very useful for identifying units, primes, and in general, reasoning about Dirichlet integers. For review of norms and conjugates, please see here.
A norm for a quadratic integer is equal to the quadratic integer multiplied by its conjugate. So, the first step in figuring out the norm is to figure out the conjugate for a given Dirichlet integer.
Let's start with a Dirichlet integer based on integers a,b:
a + b(1+√5)/2
Now, this value is equivalent to:
[(2a + b) + b√5]/2
So, the conjugate would be:
[(2a + b) - b√5]/2
To simplify, we can set a' = (2a + b), b' = b. We note that a',b' will always have the same parity. In other words, they will both be odd or they both will be even.
Using a',b', the norm is:
Norm = (a' + b'√5)/2*(a' - b'√5)/2 = (a'2 - 5b'2)/4
Putting back in (2a+b) for a' and b for b', gives us:
Norm = (a'2 - 5b'2)/4 = [(2a+b)2 - 5(b)2]/4 =
(4a2 + 4ab + b2 - 5b2)/4 =
(4a2 + 4ab - b2)/4 =
a2 + ab - b2
Unit
A unit is any quadratic integer that divides 1. Units are needed in order to establish unique factorization with quadratic integers. You can review the ideas behind units and associates by starting here.
From a previous result, we know that a unit is also any quadratic integers whose norm is ± 1.
This means that we can determine the units for Dirichlet integers by solving the following equation:
(a'2 - 5b'2)/4 = 1
Which is the same as this:
a'2 - 5b'2 = 4
This is a difficult problem. To find the solution, I will now take a short detour to talk about Pell's Equation (another difficult problem posed by Pierre de Fermat). I will then use the solution to Pell's Equation to identify the units for Dirichlet integers.
Of course, we can simplify the problem by considering a'2 - 5b'2 = -4 which is clearly a=1, b =1.
It turns out that all Dirichlet units have the same form:
±[(1 + √5)/2]±n
Lemma 2: All Dirichlet units have the following form: ±[(1 + √5)/2]±n
(1) We know that (1 + √5)/2 is a unit since:
Norm( (1 + √5)/2 ) = [(1 + √5)/2][(1 - √5)/2] = (1 - 5)/4 = -4/4 = -1
Any value that has a norm = ±1 is a unit. [See here for proof]
(2) Assume that there existed a unit α that does not have the above form.
(3) Let ω = (1 + √5)/2
(4) So, we know that there exists some integer n such that:
α is greater than ωn and is less than ωn+1
(5) We know that ωn is a unit and ωn+1 is a unit since Norm(xn) = Norm(x)*Norm(x)*...*Norm(x) = (± 1)(± 1)*...*(± 1)
(6) Since a unit by definition divides 1, we know that ω-(n) is a unit since ωn is a unit.
(7) Likewise, we know that any unit divides any other unit, so we can divide all values by ωn which gives us:
1 is less than α which is less than ω
(8) But there is no such unit that is between 1 and ω
(a) Let's assume that there is was such a unit β
(b) So, there exists two rational integers: x,y such that β = (x + y√5)/2 that is greater than 1 and less than ω
(c) And (x + y√5) is greater than 2 and less than 2*ω which is less than 4.
(d) Now, since β is a unit, we know that Norm(β) = ± 1 = [(x + y√5)/2][(x - y√5)/2]
(e) This means that x = 1 or x = 2 since:
Case I: [(x + y√5)/2][(x - y√5)/2] = 1
Since (x + y√5)/2 is greater than 1, then (x - y√5)/2 is greater than 0 and less than 1.
So, x - y√5 is greater than 0 and less than 2.
So (x + y√5 + x - y√5) is greater than 2 and less than 6.
So 2x is greater than 2 and less than 6
So x = 2.
Case II: [(x + y√5)/2][(x - y√5)/2] = -1
Since (x + y√5)/2 is greater than 1, then (x - y√5)/2 is greater than -1 and less than 0.
So, x - y√5 is greater than -2 and less than 0.
So (x + y√5 + x - y√5) is greater than 0 and less than 4.
So 2x is greater than 0 and less than 4
So x = 1.
(f) But x ≠ 1 since:
(1 + y√5)/2 is greater than 1 so y must be greater than 0 but then (1 + y√5)/2 cannot be less than (1 + √5)/2
(g) And x ≠ 2 since:
(2 + y√5)/2 is greater than 1 so y must be greater than 0.
(2 + y√5)/2 is less than (1 + √5)/2, so y must be less than 1.
But there is no integer between 0 and 1 so we have reached a contradiction.
QED
Primes
Lemma 3: √5 is also a prime in Z[(1 + √5)/2]
(1) exists since = (0 + 2√5)/2
(2) is prime since Norm(√5) = -5 [See Lemma 5 here]
QED
Lemma 4: 2 is a prime in Z[(1 + √5)/2]
See here for proof.
Wednesday, November 02, 2005
Fermat's Last Theorem: n = 5: Factoring a2 - 5b2
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 just interested in the mathematical details behind the proof, start here.
Today's blog continues the discusssion from here. The argument offered today comes from Harold M. Stark's An Introduction to Number Theory.
To establish the ideas behind the Key Lemmas, we will need to factor a2 - 5b2 into (a + b√5)(a - b√5). To do this, we will need unique factorization. For those who need a review of quadratic integers, start here.
Unfortunately, it turns out that Z[√5] is not characterized by unique factorization. (Note: Z[√5] notations describes the set of algebraic integers formed by a + b√5 where a,b are rational integers). To show this, I will introduce two lemmas:
Lemma 1: If a set Z[√d] is characterized by unique factorization, then 2 is not a prime.
(1) Assume that Z[√d] has unique factorization and 2 is a prime.
(2) d is either odd or even so either d or d-1 is divisible by 2.
(3) So, 2 divides (d)(d-1) = d2 - d = (d + √d)(d - √d) [Note, we can factor this up since we are assuming that Z[√d] has unique factorization]
(4) In Z[√d], 2 can't divide (d + √d) because 2 doesn't divide √d. Likewise, 2 can't divide (d - √d)
(5) But this is a contradiction, since by Euclid's Lemma (one of the properties of unique factorization), 2 must divide either (d + √d) or (d - √d) if 2 divides (d + √d)(d - √d).
(6) So we can reject our assumption.
QED
Lemma 2: if d ≡ 1 (mod 4), then Z[√d] never has unique factorization.
(1) Suppose that 2 is not a prime in Z[√d]
(2) Then, there exists values: α, β such that:
2 = αβ
(3) Now, we note that Norm(2) = (2 - 0√d)(2 + √d) = 4 [See here for review of norms and conjugates]
(4) Since 2 = αβ, we also note that 4 = Norm(α)*Norm(β)
(5) Since 2 is not a prime and since it is not a unit, we can suppose that absolute(Norm(α)) is greater than 1 and absolute(Norm(β)) is greater than 1.
(6) This means that Norm(α) and Norm(β) must be equal to ±2.
(7) Since α is in Z[√d], there must exist integers a,b such that α = a + b√d.
(8) So, Norm(α) = (a + b√d)(a - b√d) = a2 + b2d = ±2.
(9) Since d ≡ 1 (mod 4), we note that:
a2 + b2d ≡ a2 + b2(1) ≡ ±2 ≡2 (mod 4). [See here for a review of modular arithmetic]
(10) But this is impossible:
(odd) 2 ≡ (2u+1)2 ≡ 4u2 + 4u + 1 ≡ 1 (mod 4).
(even)2 ≡ (2u)2 ≡ 4u2 ≡ 0 (mod 4).
Case I: a is odd, b is odd: a2 - b2 ≡ 1 - 1 ≡ 0 (mod 4).
Case II: a is odd, b is even: a2 - b2 ≡ 1 - 0 ≡ 1 (mod 4).
Case III: a is even, b is odd: a2 - b2 ≡ 0 - 1 ≡ 3 (mod 4).
Case IV: a is even, b is even: a2 - b2 ≡ 0 - 0 ≡ 0 (mod 4).
QED
Luckily, there is a way out. From a previous result, we know that Z[(1 + √5)/2] has unique factorization.
So in my next blog, I will talk more about Z[(1 + √5)/2].
Today's blog continues the discusssion from here. The argument offered today comes from Harold M. Stark's An Introduction to Number Theory.
To establish the ideas behind the Key Lemmas, we will need to factor a2 - 5b2 into (a + b√5)(a - b√5). To do this, we will need unique factorization. For those who need a review of quadratic integers, start here.
Unfortunately, it turns out that Z[√5] is not characterized by unique factorization. (Note: Z[√5] notations describes the set of algebraic integers formed by a + b√5 where a,b are rational integers). To show this, I will introduce two lemmas:
Lemma 1: If a set Z[√d] is characterized by unique factorization, then 2 is not a prime.
(1) Assume that Z[√d] has unique factorization and 2 is a prime.
(2) d is either odd or even so either d or d-1 is divisible by 2.
(3) So, 2 divides (d)(d-1) = d2 - d = (d + √d)(d - √d) [Note, we can factor this up since we are assuming that Z[√d] has unique factorization]
(4) In Z[√d], 2 can't divide (d + √d) because 2 doesn't divide √d. Likewise, 2 can't divide (d - √d)
(5) But this is a contradiction, since by Euclid's Lemma (one of the properties of unique factorization), 2 must divide either (d + √d) or (d - √d) if 2 divides (d + √d)(d - √d).
(6) So we can reject our assumption.
QED
Lemma 2: if d ≡ 1 (mod 4), then Z[√d] never has unique factorization.
(1) Suppose that 2 is not a prime in Z[√d]
(2) Then, there exists values: α, β such that:
2 = αβ
(3) Now, we note that Norm(2) = (2 - 0√d)(2 + √d) = 4 [See here for review of norms and conjugates]
(4) Since 2 = αβ, we also note that 4 = Norm(α)*Norm(β)
(5) Since 2 is not a prime and since it is not a unit, we can suppose that absolute(Norm(α)) is greater than 1 and absolute(Norm(β)) is greater than 1.
(6) This means that Norm(α) and Norm(β) must be equal to ±2.
(7) Since α is in Z[√d], there must exist integers a,b such that α = a + b√d.
(8) So, Norm(α) = (a + b√d)(a - b√d) = a2 + b2d = ±2.
(9) Since d ≡ 1 (mod 4), we note that:
a2 + b2d ≡ a2 + b2(1) ≡ ±2 ≡2 (mod 4). [See here for a review of modular arithmetic]
(10) But this is impossible:
(odd) 2 ≡ (2u+1)2 ≡ 4u2 + 4u + 1 ≡ 1 (mod 4).
(even)2 ≡ (2u)2 ≡ 4u2 ≡ 0 (mod 4).
Case I: a is odd, b is odd: a2 - b2 ≡ 1 - 1 ≡ 0 (mod 4).
Case II: a is odd, b is even: a2 - b2 ≡ 1 - 0 ≡ 1 (mod 4).
Case III: a is even, b is odd: a2 - b2 ≡ 0 - 1 ≡ 3 (mod 4).
Case IV: a is even, b is even: a2 - b2 ≡ 0 - 0 ≡ 0 (mod 4).
QED
Luckily, there is a way out. From a previous result, we know that Z[(1 + √5)/2] has unique factorization.
So in my next blog, I will talk more about Z[(1 + √5)/2].
Tuesday, November 01, 2005
Fermat's Last Theorem: Proof for n = 5: Key Lemmas
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 just interested in the mathematical details behind the proof, start here.
Today's blog continues the proof on Fermat's Last Theorem: n=5 by offering two lemmas that are really the crucial idea behind the proof. Both lemmas rest on foundations of continued fractions and quadratic integers.
Lemma 1:
Given two integers a,b such that:
(a) gcd(a,b)=1
(b) a,b have different parities (one is odd, one is even)
(c) 5 doesn't divide a
(d) 5 divides b
(e) (a2 - 5b2) is a fifth power.
Then there exists two integers c,d such that:
(i) a = c(c4 + 50c2d2 + 125d4)
(ii) b = 5d(c4 + 10c2d2 + 5d4)
(iii) gcd(c,d)=1
(iv) c,d have different parities
(v) 5 doesn't divide c
(vi) 5 does divide d
(vii) c,d are nonzero
Proof:
(1) Assume that gcd(a + b√5, a - b√5)= d which is greater than 1.
(2) Then there exists e,f such that:
de = a + b√5
df = a - b√5
(3) a + b√5 + a - b√5 = 2a = de + df = d(e + f)
(4) Likewise a + b√5 - (a - b√5) = 2b√5 = d(e - f)
(5) Now d doesn't divide √5 since:
(a) √5 is a prime (see here).
(b) So if d divides it, it would have to = √5
(c) But d divides 2a (from #3)
(d) Which would mean √5 divides 2a which means 5 divides 4a2
(e) Which is impossible since 5 doesn't divide a.
(6) So d divides 2b.
(7) So d must divide 2 since it divides 2a and 2b but gcd(a,b)=1.
(8) Now 2 is prime so d=2. (See here)
(9) This means that 4 divides (a + b√5)(a - b√5) = a2 - 5b2
(10) But this is impossible since a,b have different parities:
(odd) - 5(even) = odd - even = odd
(even) - 5(odd) = even - odd = odd
So we reject our assumption.
(11) Since Z[(1 + √5)/2] has unique factorization (see here), we can conclude that a + b√5 and a - b√5 are fifth powers (see here ).
(12) This means that there exists m,n,t,u such that a + b√5 = [(m + n√5)/2]5[(t + u√5)/2] where (t + u√5)/2 is a unit.
(13) Now, if u = 0, then we reach our conclusion (see here). If u ≠ 0, we reach our conclusion (see here )
QED
Lemma 2:
Given two integers a,b such that:
(a) gcd(a,b)=1
(b) a,b are both odd
(c) 5 doesn't divide a
(d) 5 divides b
(e) (a2 - 5b2)/4 is a fifth power.
Then there exists two integers c,d such that:
(i) a = c(c4 + 50c2d2 + 125d4)/16
(ii) b = 5d(c4 + 10c2d2 + 5d4)/16
(iii) gcd(c,d)=1
(iv) c,d are both odd
(v) 5 doesn't divide c
(vi) 5 divides d
(vii) c,d are nonzero.
(1) Assume that gcd([a + b√5]/2, [a - b√5]/2)= d which is greater than 1.
(2) Then there exists e,f such that:
de = (a + b√5)/2
df = (a - b√5)/2
(3) (a + b√5)/2 + (a - b√5)/2= a = de + df = d(e + f)
(4) Likewise (a + b√5)/2 - (a - b√5)/2 = b√5 = d(e - f)
(5) Now d doesn't divide √5 since:
(a) √5 is a prime (see here).
(b) So if d divides it, it would have to = √5
(c) But d divides a (from #3)
(d) Which is impossible since 5 doesn't divide a.
(6) So d divides b.
(7) But this is impossible since gcd(a,b)=1.
So we reject our assumption.
(8) Since Z[(1 + √5)/2] has unique factorization (see here -- to be added later), we can conclude that (a + b√5)/2 and (a - b√5)/2 are fifth powers (see here -- to be added later).
(9) This means that there exists m,n,t,u such that (a + b√5)/2 = [(m + n√5)/2]5[(t + u√5)/2] where (t + u√5)/2 is a unit.
(13) Now, if u = 0, then we reach our conclusion (see here ). If u ≠ 0, we reach our conclusion (see here )
QED
To show the proof for these lemmas, it needs to be possible to factor a2 - 5b2 into (a - b√5)(a + b√5) [See here for details on unique factorization and the existence of √5 as a prime].
To avoid making Euler's mistake, we will need to make sure that Z[√5] or some variant such as Z[(1 + √5)/2] is characterized by unique factorization. More details can be found here.
Today's blog continues the proof on Fermat's Last Theorem: n=5 by offering two lemmas that are really the crucial idea behind the proof. Both lemmas rest on foundations of continued fractions and quadratic integers.
Lemma 1:
Given two integers a,b such that:
(a) gcd(a,b)=1
(b) a,b have different parities (one is odd, one is even)
(c) 5 doesn't divide a
(d) 5 divides b
(e) (a2 - 5b2) is a fifth power.
Then there exists two integers c,d such that:
(i) a = c(c4 + 50c2d2 + 125d4)
(ii) b = 5d(c4 + 10c2d2 + 5d4)
(iii) gcd(c,d)=1
(iv) c,d have different parities
(v) 5 doesn't divide c
(vi) 5 does divide d
(vii) c,d are nonzero
Proof:
(1) Assume that gcd(a + b√5, a - b√5)= d which is greater than 1.
(2) Then there exists e,f such that:
de = a + b√5
df = a - b√5
(3) a + b√5 + a - b√5 = 2a = de + df = d(e + f)
(4) Likewise a + b√5 - (a - b√5) = 2b√5 = d(e - f)
(5) Now d doesn't divide √5 since:
(a) √5 is a prime (see here).
(b) So if d divides it, it would have to = √5
(c) But d divides 2a (from #3)
(d) Which would mean √5 divides 2a which means 5 divides 4a2
(e) Which is impossible since 5 doesn't divide a.
(6) So d divides 2b.
(7) So d must divide 2 since it divides 2a and 2b but gcd(a,b)=1.
(8) Now 2 is prime so d=2. (See here)
(9) This means that 4 divides (a + b√5)(a - b√5) = a2 - 5b2
(10) But this is impossible since a,b have different parities:
(odd) - 5(even) = odd - even = odd
(even) - 5(odd) = even - odd = odd
So we reject our assumption.
(11) Since Z[(1 + √5)/2] has unique factorization (see here), we can conclude that a + b√5 and a - b√5 are fifth powers (see here ).
(12) This means that there exists m,n,t,u such that a + b√5 = [(m + n√5)/2]5[(t + u√5)/2] where (t + u√5)/2 is a unit.
(13) Now, if u = 0, then we reach our conclusion (see here). If u ≠ 0, we reach our conclusion (see here )
QED
Lemma 2:
Given two integers a,b such that:
(a) gcd(a,b)=1
(b) a,b are both odd
(c) 5 doesn't divide a
(d) 5 divides b
(e) (a2 - 5b2)/4 is a fifth power.
Then there exists two integers c,d such that:
(i) a = c(c4 + 50c2d2 + 125d4)/16
(ii) b = 5d(c4 + 10c2d2 + 5d4)/16
(iii) gcd(c,d)=1
(iv) c,d are both odd
(v) 5 doesn't divide c
(vi) 5 divides d
(vii) c,d are nonzero.
(1) Assume that gcd([a + b√5]/2, [a - b√5]/2)= d which is greater than 1.
(2) Then there exists e,f such that:
de = (a + b√5)/2
df = (a - b√5)/2
(3) (a + b√5)/2 + (a - b√5)/2= a = de + df = d(e + f)
(4) Likewise (a + b√5)/2 - (a - b√5)/2 = b√5 = d(e - f)
(5) Now d doesn't divide √5 since:
(a) √5 is a prime (see here).
(b) So if d divides it, it would have to = √5
(c) But d divides a (from #3)
(d) Which is impossible since 5 doesn't divide a.
(6) So d divides b.
(7) But this is impossible since gcd(a,b)=1.
So we reject our assumption.
(8) Since Z[(1 + √5)/2] has unique factorization (see here -- to be added later), we can conclude that (a + b√5)/2 and (a - b√5)/2 are fifth powers (see here -- to be added later).
(9) This means that there exists m,n,t,u such that (a + b√5)/2 = [(m + n√5)/2]5[(t + u√5)/2] where (t + u√5)/2 is a unit.
(13) Now, if u = 0, then we reach our conclusion (see here ). If u ≠ 0, we reach our conclusion (see here )
QED
To show the proof for these lemmas, it needs to be possible to factor a2 - 5b2 into (a - b√5)(a + b√5) [See here for details on unique factorization and the existence of √5 as a prime].
To avoid making Euler's mistake, we will need to make sure that Z[√5] or some variant such as Z[(1 + √5)/2] is characterized by unique factorization. More details can be found here.
Subscribe to:
Posts (Atom)
