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
Subscribe to:
Post Comments (Atom)
5 comments:
In Lemma 2 (3):
Shouldn't you be factoring the qn+1 and pn+1?
Rob
Hi Rob,
Thanks very much for your question. I've rewritten Lemma 2 to make it clearer. I hope that this answers your question.
Cheers,
-Larry
In step (4) of Theorem 1:
[(an+1)pn+pn-1]/(an+1)qn+qn-1
should be:
[(an+1)pn + pn-1]/[(an+1)qn+qn-1]
In step (4) of Theorem 2
Should
We also know that α-pn is greater than 0
be
We also know that α - pn/qn is greater than 0
Rob
In step (4) of Lemma 5
an(pn-1qn-2-pn-2qn-1)=ak(-1)^n-2
Should be
an(pn-1qn-2-pn-2qn-1)=an(-1)^n-2
Post a Comment