In today's blog, I will go over some lemmas that are needed to complete the solution to Pell's Equation using purely periodic continued fractions.
The lemmas in today's proof is taken from Heinrich Dorrie's 100 Great Problems of Elementary Mathematics.
Lemma 1: Let D = 4n and let g = floor(√n). The coefficients for a reduced quadratic equation are: a = 1, b = -2g, c = g2 - n.
(1) The discriminant D = b2 - 4ac (see here for review)
(2) We know that r + b is less than 2a which is less than r - b since:
(a) 2√n - 2g is less than 2 [since we defined g as the floor of √n, we know that this value - g is less than 1.
(b) We also know that 2 is less than 2√n + 2g since √n + g is greater than 1.
(c) Since r = 2√n and since we are assuming that b = -2g, r + b = 2√n - 2g and likewise r - b = 2√n + 2g
(3) This proves tht we have a reduced fraction since:
-(r + b)/2a is a negative proper fraction
r - b/2a is a positive improper fraction.
QED
Lemma 2: Let D = 4n + 1. Let g be the largest integer for which g2 + g will be smaller than n [so that, (g + 1)2 + (g+1) is greater than n]. In this case, setting a = 1, b = -(2g + 1), c = g2 + g - n gives us a reduced quadratic equation.
(1) First, we note that √D - (2g + 1) is less than 2.
(a) From our assumption about g2 + g, we know that (g + 1)2 + (g+1) is greater than n and that:
(g+1)2 + g + 1 = g2 + 2g + 1 + g + 1 = g2 + 3g + 2
(b) Multiplying the above by 4 and adding 1 to each side gives us:
4g2 + 12g + 9 is greater than 4n + 1.
(c) So that we have:
(2g + 3)2 is greater than D.
(d) From this, it follows that 2g + 3 is greater than √D
(e) Rearranging this gives us:
√D - (2g + 1) is less than 2.
(2) 2 is less than √D + 2g + 1 since:
D ≥ 1 and g≥ 1.
(3) We then have r + b is less than 2a since:
r = √D and b = -(2g + 1)
(4) We also have 2a is less than r - b.
(5) So using the same reasoning in Lemma 1 we are done.
QED
Saturday, January 14, 2006
Tuesday, January 10, 2006
Pell's Equation: The Solution with Reduced Quadratic Equations
In a previous blog, I showed how combining 2x2 matrices with continued fractions can lead to a solution to Pell's Equation (see here).
In today's blog, I will show a solution that uses purely periodic continued fractions. Most of today's proof is based on Heinrich Dorrie's: 100 Great Problems of Elementary Mathematics.
The important idea in today's solution is the two concepts purely periodic continued fractions and reduced quadratic equations.
A purely periodic continued fraction is a continued fraction where the entire continued fraction is repeated. In other words, the continued fraction has this form: [a0, a1, ..., an-1 ].
A periodic continued fraction is not purely periodic if not all the elements repeat. For example, the following periodic continued fraction is not purely periodic: [ a0, a1, a2, ..., an-1 ].
A reduced quadratic equation is a quadratic equation that has relatively prime, integer coefficients, a squarefree discriminant, a first root which is a positive, improper fraction, and a second root which is a negative, proper fraction. (See here for details)
We start with a lemma that will be needed in the solution.
Lemma 1: if there exists two different quadratic equations with the same solution such that we have:
(a) au2 + bu + c = 0, gcd(a,b,c)=1, a,b,c are integers
(b) a'u2 + b'u + c' = 0, a' ≠ a, b' ≠ b, c' ≠ c, and a', b', c' integers
Then, there exists an integer y such that y = a'/a = b'/b = c'/c.
(1) Let y = c'/c so that c' = cy
(2) From (a), we know that -c/u = au + b since:
-c = au2 + bu = u(au + b)
(3) From (b), we know that -c'/u = a'u + b' for the same reason.
(4) From (1) and (3), we have -cy/u = a'u + b' which gives us:
-c/u = (a'u + b')/y = a'u/y + b'/y
(5) Applying (4) with (2) gives us:
au + b = -c/u = a'u/y + b'/y
(6) One possible solution to (5) is to assume:
au = a'u/y
b = b'/y
(7) Combining (6) with (1) gives us:
c'/c = a'/a = b'/b = y
(8) Now, we need to show that y is an integer.
(9) Assume that y is not an integer.
(10) Then there exist integers u,v such that gcd(u,v)=1 and y=u/v
We can assume that gcd(u,v)=1 since if it is not, we can factor out any common primes.
(11) From (9), we can assume that v ≠ 1.
(12) So u/v = c'/c = a'/a = b'/b
(13) So c'v = cu which implies that v divides c (since gcd(u,v)=1).
(14) And b'v = bu implies that v divides b
(15) But gcd(b,c)=1 (from our assumption) so we have a contradiction and we can reject #9.
QED
Theorem 1: A reduced quadratic equation can be used to solve x2 - dy2 = 4
(1) Let [ a1, a2, ... an, a1, ... an ] be the representation of a reduced quadratic equation au2 + bu + c = 0 where n is the period and whose discriminant D = d. [See here for proof that a reduced quadratic equation results in a purely periodic continued fraction]
(2) Let N is be an even multiple of n. For purposes of this proof, we can assume that N = 2n.
(3) Let P/Q = [ a1, ... an ... aN ]
(4) Let p/q = [ a1, ... an ... aN-1 ]
(5) From a previous result and (1) we know that;
u = (Pu + p)/(Qu + q) [see here]
So that:
Qu2 + qu - Pu - p = 0
(6) Let H = P - q
(7) We then have the following form for (5)
Qu2 - Hu - p = 0
(8) From the lemma above, we know that there exists y such that:
y = Q/a = P-q/-b = p/-c
(9) We can also define a value x such that x = P + q
(10) From (8), -by = P-q
(11) Combining (9) and (10) gives us:
x2 - b2y2 = (P + q)2 - (P-q)2
(12) From (8):
4acy2 = 4ac(Q/a)(p/-c) = -4Qp
(13) Since D = b2 - 4ac, we have:
x2 - dy2 = x2 - Dy2 =
= x2 - (b2 - 4ac)y2 =
= x2 - b2y2 + 4acy2
(14) Combining (13) with (11) and (12) gives us:
x2 - dy2 = (P + q)2 - (P - q)2 - 4Qp =
= 4Pq - 4Qp = 4(Pq - Qp)
(15) We know that Pq - Qp = 1 (see Step #4 in Theorem 2 below), so that we have now proven that using a reduced equation of D = d gives us:
x2 - dy2 = 4(Pq - Qp) = 4(1) = 4
QED
Corrolary 1.1: This equation can be used to solve Pell's Equation
(1) Pell's equation refers to the equation: x2 - dy2 = 1.
(2) Let x' = 2x, d' = 4d.
(3) Use the above theorem to solve:
(x')2 - (d')y2 = 4
This means that:
(2x)2 - (4d)y2 =4x2 - 4dy2 = 4
Which dividing all sides by 4 implies:
x2 - dy2 = 1.
QED
Theorem 2: Every solution to the equation x2 - dy2 = 4 is solved by the method in Thereom 1.
(1) Let x, y be a solution to x2 - dy2 = 4.
(2) We know that there exists a reduced quadratic equation that has a discriminant = D (see here for proof) such that:
au2 + bu + c = 0.
(3) We can define four values: P,Q,p,q such that:
P = (x - by)/2
Q = ay
p = -cy
q = (x + by)/2
(4) We note that Pq - Qp = 1 since
(x-by)/2 * (x+by)/2 - (ay)(-cy) = [x2 - b2y2]/4 + acy2 =
= [x2 - b2y2 + 4acy2]/4 =
= [x2 - (b2 - 4ac)y2]/4 =
= [x2 - dy2]/4
(5) Now applying #1 to #4 gives us:
Pq - Qp = [x2 - dy2]/4 = 4/4 = 1
(6) From #3, we have:
a = Q/y [from Q=ay]
b = -(P-q)/y [from q-P = (x + by)/2 - (x-by)/2 = 2by/2 = by --> b = -(P-q)/y]
c = -p/y [from p=-cy]
(7) Applying this to #2 gives us:
(Q/y)u2 + [-(P-q)/y]u + -p/y = 0
(8) Multiplying all sides by y gives us:
Qu2 -Pu + qu -p = 0
(9) Which implies:
Qu2 + qu = Pu + p
(10) And then:
u = (Pu + p)/(Qu + q)
(11) Finally we, prove that Q ≥ q
(a) From #3, we know that
2(Q - q) = 2(ay - [x + by]/2) = 2ay - x -by = [2a - b]y - x
(b) Since the second root of #2 is a negative proper fraction (see here for definition of reduced quadratic equation), we have:
-(-r -b) is less than 2a which implies that r + b is less than 2a and that 2a - b is greater than r.
(c) Since r2 = d (see here for definition of discriminant) and using #1, we get:
r2y2 - x2 = -1(x2 - dy2) = -4
(d) So:
2(Q -q) is greater than ry - x = (r2y2 - x2)/(ry+x) = -4/(ry + x) which simplifies to: (Q - q) is greater than -2/(ry + x)
(e) We know that D is a squarefree, positive integer so D ≥ 2 so r is greater than 1.
(f) We know that y is at least 1 (since we are ignoring the trivial solution: x=2,y=0). We know that x is at least 3 since it must be greater than √2*1 + 4 which means that x ≥ 3.
(g) This gives us Q - q is greater than -2/(2+3) = -2/(5) = -0.4. That is Q ≥ q (since Q is an integer and q is an improper fraction over 2).
(12) Since P/Q is a rational number, we can represent it as a finite continued fraction (see here) and we can assume that n is even (see Lemma 3 here)
Let's say P/Q = [ a1, a2, ..., an ]
(13) Let p'/q' be the approximation that comes just before P/Q.
(14) Then Pq' - Qp' = 1. [See here for details]
(15) If we subtract #5 from #14, we get:
Pq' - Qp' - (Pq - Qp) = P(q' - q) - Q(p' - p) = 1 - 1 = 0
(16) This implies that:
P(q' - q) = Q(p' - p).
(17) Since gcd(P,Q)=1 (see Lemma 6 here), since q ≤ Q (see #11) and q' is less than Q (see here), then:
q' = q (since Q ≥ q' and Q divides q' - q) and since Q ≠ 0, p' = p.
(18) From all this we can conclude that:
[ a1, ..., an, u ] = (Pu + p)/(Qu + q) [ See here for proof ]
(19) Apply #10 gives us;
u = [ a1, ..., an, u ]
(20) Hence, as we can see each value x,y can in this way be gotten from the expansion of the reduced number u.
QED
Finally, I present an example that shows this method in action.
Example: Find the smallest solution for x2 - 112y2 = 4.
(1) We first find a reduced quadratic equation where the discriminant = 112. Let's use:
3u2 - 10u - 1 = 0.
D = b2 - 4ac = (-10)2 - 4(3)(-1) = 100 + 12 = 112
(2) We generate the continued fraction for this equation (see here for method):
u = [ 3, 2, 3, 10, ... ]
(3) In this case the period length is 4 so we take the first four approximate fractions (see here for method):
p1 = 3
p2 = 7
p3 = 24
p4 = 247
q1 = 1
q2 = 2
q3 = 7
q4 = 72
x = P + q = 247 + 7 = 254
y = Q/a = 72/3 = 24.
(254)2 - 112(24)2 = 64,516 - 112(576) = 64,516 - 64,512 = 4.
QED
In today's blog, I will show a solution that uses purely periodic continued fractions. Most of today's proof is based on Heinrich Dorrie's: 100 Great Problems of Elementary Mathematics.
The important idea in today's solution is the two concepts purely periodic continued fractions and reduced quadratic equations.
A purely periodic continued fraction is a continued fraction where the entire continued fraction is repeated. In other words, the continued fraction has this form: [a0, a1, ..., an-1 ].
A periodic continued fraction is not purely periodic if not all the elements repeat. For example, the following periodic continued fraction is not purely periodic: [ a0, a1, a2, ..., an-1 ].
A reduced quadratic equation is a quadratic equation that has relatively prime, integer coefficients, a squarefree discriminant, a first root which is a positive, improper fraction, and a second root which is a negative, proper fraction. (See here for details)
We start with a lemma that will be needed in the solution.
Lemma 1: if there exists two different quadratic equations with the same solution such that we have:
(a) au2 + bu + c = 0, gcd(a,b,c)=1, a,b,c are integers
(b) a'u2 + b'u + c' = 0, a' ≠ a, b' ≠ b, c' ≠ c, and a', b', c' integers
Then, there exists an integer y such that y = a'/a = b'/b = c'/c.
(1) Let y = c'/c so that c' = cy
(2) From (a), we know that -c/u = au + b since:
-c = au2 + bu = u(au + b)
(3) From (b), we know that -c'/u = a'u + b' for the same reason.
(4) From (1) and (3), we have -cy/u = a'u + b' which gives us:
-c/u = (a'u + b')/y = a'u/y + b'/y
(5) Applying (4) with (2) gives us:
au + b = -c/u = a'u/y + b'/y
(6) One possible solution to (5) is to assume:
au = a'u/y
b = b'/y
(7) Combining (6) with (1) gives us:
c'/c = a'/a = b'/b = y
(8) Now, we need to show that y is an integer.
(9) Assume that y is not an integer.
(10) Then there exist integers u,v such that gcd(u,v)=1 and y=u/v
We can assume that gcd(u,v)=1 since if it is not, we can factor out any common primes.
(11) From (9), we can assume that v ≠ 1.
(12) So u/v = c'/c = a'/a = b'/b
(13) So c'v = cu which implies that v divides c (since gcd(u,v)=1).
(14) And b'v = bu implies that v divides b
(15) But gcd(b,c)=1 (from our assumption) so we have a contradiction and we can reject #9.
QED
Theorem 1: A reduced quadratic equation can be used to solve x2 - dy2 = 4
(1) Let [ a1, a2, ... an, a1, ... an ] be the representation of a reduced quadratic equation au2 + bu + c = 0 where n is the period and whose discriminant D = d. [See here for proof that a reduced quadratic equation results in a purely periodic continued fraction]
(2) Let N is be an even multiple of n. For purposes of this proof, we can assume that N = 2n.
(3) Let P/Q = [ a1, ... an ... aN ]
(4) Let p/q = [ a1, ... an ... aN-1 ]
(5) From a previous result and (1) we know that;
u = (Pu + p)/(Qu + q) [see here]
So that:
Qu2 + qu - Pu - p = 0
(6) Let H = P - q
(7) We then have the following form for (5)
Qu2 - Hu - p = 0
(8) From the lemma above, we know that there exists y such that:
y = Q/a = P-q/-b = p/-c
(9) We can also define a value x such that x = P + q
(10) From (8), -by = P-q
(11) Combining (9) and (10) gives us:
x2 - b2y2 = (P + q)2 - (P-q)2
(12) From (8):
4acy2 = 4ac(Q/a)(p/-c) = -4Qp
(13) Since D = b2 - 4ac, we have:
x2 - dy2 = x2 - Dy2 =
= x2 - (b2 - 4ac)y2 =
= x2 - b2y2 + 4acy2
(14) Combining (13) with (11) and (12) gives us:
x2 - dy2 = (P + q)2 - (P - q)2 - 4Qp =
= 4Pq - 4Qp = 4(Pq - Qp)
(15) We know that Pq - Qp = 1 (see Step #4 in Theorem 2 below), so that we have now proven that using a reduced equation of D = d gives us:
x2 - dy2 = 4(Pq - Qp) = 4(1) = 4
QED
Corrolary 1.1: This equation can be used to solve Pell's Equation
(1) Pell's equation refers to the equation: x2 - dy2 = 1.
(2) Let x' = 2x, d' = 4d.
(3) Use the above theorem to solve:
(x')2 - (d')y2 = 4
This means that:
(2x)2 - (4d)y2 =4x2 - 4dy2 = 4
Which dividing all sides by 4 implies:
x2 - dy2 = 1.
QED
Theorem 2: Every solution to the equation x2 - dy2 = 4 is solved by the method in Thereom 1.
(1) Let x, y be a solution to x2 - dy2 = 4.
(2) We know that there exists a reduced quadratic equation that has a discriminant = D (see here for proof) such that:
au2 + bu + c = 0.
(3) We can define four values: P,Q,p,q such that:
P = (x - by)/2
Q = ay
p = -cy
q = (x + by)/2
(4) We note that Pq - Qp = 1 since
(x-by)/2 * (x+by)/2 - (ay)(-cy) = [x2 - b2y2]/4 + acy2 =
= [x2 - b2y2 + 4acy2]/4 =
= [x2 - (b2 - 4ac)y2]/4 =
= [x2 - dy2]/4
(5) Now applying #1 to #4 gives us:
Pq - Qp = [x2 - dy2]/4 = 4/4 = 1
(6) From #3, we have:
a = Q/y [from Q=ay]
b = -(P-q)/y [from q-P = (x + by)/2 - (x-by)/2 = 2by/2 = by --> b = -(P-q)/y]
c = -p/y [from p=-cy]
(7) Applying this to #2 gives us:
(Q/y)u2 + [-(P-q)/y]u + -p/y = 0
(8) Multiplying all sides by y gives us:
Qu2 -Pu + qu -p = 0
(9) Which implies:
Qu2 + qu = Pu + p
(10) And then:
u = (Pu + p)/(Qu + q)
(11) Finally we, prove that Q ≥ q
(a) From #3, we know that
2(Q - q) = 2(ay - [x + by]/2) = 2ay - x -by = [2a - b]y - x
(b) Since the second root of #2 is a negative proper fraction (see here for definition of reduced quadratic equation), we have:
-(-r -b) is less than 2a which implies that r + b is less than 2a and that 2a - b is greater than r.
(c) Since r2 = d (see here for definition of discriminant) and using #1, we get:
r2y2 - x2 = -1(x2 - dy2) = -4
(d) So:
2(Q -q) is greater than ry - x = (r2y2 - x2)/(ry+x) = -4/(ry + x) which simplifies to: (Q - q) is greater than -2/(ry + x)
(e) We know that D is a squarefree, positive integer so D ≥ 2 so r is greater than 1.
(f) We know that y is at least 1 (since we are ignoring the trivial solution: x=2,y=0). We know that x is at least 3 since it must be greater than √2*1 + 4 which means that x ≥ 3.
(g) This gives us Q - q is greater than -2/(2+3) = -2/(5) = -0.4. That is Q ≥ q (since Q is an integer and q is an improper fraction over 2).
(12) Since P/Q is a rational number, we can represent it as a finite continued fraction (see here) and we can assume that n is even (see Lemma 3 here)
Let's say P/Q = [ a1, a2, ..., an ]
(13) Let p'/q' be the approximation that comes just before P/Q.
(14) Then Pq' - Qp' = 1. [See here for details]
(15) If we subtract #5 from #14, we get:
Pq' - Qp' - (Pq - Qp) = P(q' - q) - Q(p' - p) = 1 - 1 = 0
(16) This implies that:
P(q' - q) = Q(p' - p).
(17) Since gcd(P,Q)=1 (see Lemma 6 here), since q ≤ Q (see #11) and q' is less than Q (see here), then:
q' = q (since Q ≥ q' and Q divides q' - q) and since Q ≠ 0, p' = p.
(18) From all this we can conclude that:
[ a1, ..., an, u ] = (Pu + p)/(Qu + q) [ See here for proof ]
(19) Apply #10 gives us;
u = [ a1, ..., an, u ]
(20) Hence, as we can see each value x,y can in this way be gotten from the expansion of the reduced number u.
QED
Finally, I present an example that shows this method in action.
Example: Find the smallest solution for x2 - 112y2 = 4.
(1) We first find a reduced quadratic equation where the discriminant = 112. Let's use:
3u2 - 10u - 1 = 0.
D = b2 - 4ac = (-10)2 - 4(3)(-1) = 100 + 12 = 112
(2) We generate the continued fraction for this equation (see here for method):
u = [ 3, 2, 3, 10, ... ]
(3) In this case the period length is 4 so we take the first four approximate fractions (see here for method):
p1 = 3
p2 = 7
p3 = 24
p4 = 247
q1 = 1
q2 = 2
q3 = 7
q4 = 72
x = P + q = 247 + 7 = 254
y = Q/a = 72/3 = 24.
(254)2 - 112(24)2 = 64,516 - 112(576) = 64,516 - 64,512 = 4.
QED
Sunday, January 08, 2006
Continued Fractions: Purely Periodic Continued Fractions
In a previous blog, I showed a solution to Pell's Equation using continued fractions and matrices. One might reasonably ask if there is a simpler solution. It turns out that if we use the concept of purely periodic continued fractions, we can solve Pell's Equation using continued fractions but without needing to use matrix theory.
For those not familiar with continued fractions, start here. For those who are not familiar with Pell's Equation, start here. For those not familiar with how Pell's Equation fits into Fermat's Last Theorem, see here.
Today's blog is based on Heinrich Dorrie's 100 Great Problems of Elementary Mathematics.
In a previous blog, I showed that a continued fraction is periodic if and only if it represents the root of a quadratic equation (see here).
A purely periodic continued fraction is a continued fraction where the entire fraction a0 through an repeats. Here are some examples:
(a) This continued fraction is periodic but not purely periodic.
√6 = [ 2, 2, 4 ] (see here)
(b) This continued fraction is purely periodic.
√112 + 10/ 6 = [ 3, 2, 3, 10 ]
Just as periodic continued fractions correspond to quadratic equations, it turns out that purely periodic continued fractions correspond to what we will call "reduced" quadratic equations.
Definition: A reduced quadratic equation is any quadratic equation where the first root is a positive irrational greater than 1, its second root is a negative irrational that is greater than -1 and less than 0, and the discriminant is a nonsquare integer.
The discriminant refers to D in the following equation (see here):
x = (-b ± √d)/2a =(-b ± √b2 - 4ac)/2a
So the discriminant D is always equal to: b2 - 4ac.
In other words, the first root is a positive improper fraction (a fraction whose numerator is larger than or equal to its denominator such as 11/4 or 3/3) and the second root is a negative proper fraction (a fraction whose numerator is less than its denominator such as 1/2 or 1/3).
In my next blog, I will show how purely periodic continued fractions can be used to solve Pell's Equation.
Lemma 1: Every purely periodic continued fraction is a representation of a reduced quadratic equation.
(1) Let α be the purely periodic continued fraction with period n:
α = [ a1, a2, ...., an, a1, ... ]
(2) Let N be an even multiple of n such that we have:
α = [ a1, a2,, ..., aN, α ]
(3) We can assume that a1, a2, ... are integers greater than 0. [See here]
(4) Let P/Q be the Nth approximation of this continued fraction such that:
P/Q = [ a1, a2, ..., aN ]
(5) Let p/q be the (N-1)th approximation of this continued fraction such that:
p/q = [ a1, a2, ..., aN-1 ]
(6) According to previous results:
(a) Pq - Qp = 1 (see Lemma 2 here)
(b) α = (Pα + p)/(Qα + q) (see Lemma 1 here)
(c) α lies in between P/Q and p/q. It is greater than one and less than the other. (see Corollary 5.2 here )
(7) Rearranging (6b) gives us:
Qα2 + qα - Pα - p = 0.
(8) If we set H = P - q, we get:
Qα2 - Hα - p = 0.
(9) Solving for α gives us two roots such that:
α = H ± √H2 + 4Qp/(2Q)
(10) The discriminant D = H2 + 4Qp (see definition above) which means:
D = H2 + 4Pq - 4 = (P + q)2 - 4.
This shows that D is not a square (see here for proof )
(11) Let r = √D
(12) If we set α as the first root and α as the second root, we see that:
α = (H + r)/2Q
α = (H - r)/2Q
(13) We also note that r is greater than H since r = H2 + 4Qp and 4Qp ≥ 4 (see here)
(14) So we know that α is positive and that α is negative (since r,Q are ≥ 1; Q is greater than 1 by above)
(15) We know that α is an improper fraction since in order for it to repeat, it needs to be equal to the reciprocal of a proper fraction (that is, 1/[α - floor(α)] ) so that all we have left is to prove that α is a proper fraction.
(16) α * α = (H+r)(H-r)/[(2Q)(2Q)] = H2 - r2/4Q2 =
=( H2 - [H2 + 4Qp])/4Q2 =
-4Qp/4Q2 = -p/Q
(17) So α = (p/Q)/α
(18) Since P is greater than p (see Corollary 4.2, here), Q is greater than q (see Lemma 4 here), we have:
- α is less than (P/Q)/α and less than (p/q)/α
(19) But since α lies between P/Q and p/q (see #6c above), we know that one value is greater than α and one value is less than α.
(20) A value less over α is a proper fraction and we have shown that - α lies between 0 and a proper fraction. So, therefore, it must be a proper fraction.
(21) We have thus proven that α is a reduced number -- that is, it is the root a reduced equation (see definition above)
QED
Lemma 2: All irrational numbers that result from the continued fraction expansion of a reduced number are themselves solutions to a quadratic equation.
(1) Let α be a reduced number.
That is, it is an improper fraction solution to:
ax2 + bx + c = 0
Where: a,b,c are relatively prime integers and α is a negative proper fraction.
(2) For the start of the expansion, we note that:
α' = 1/(α - g)
That is: g is the largest whole number less than α and α' is the first derivative from α. In this case, g corresponds to a0 of the continued fraction.
(3) Let's also define a', b', c' such that:
a' = -ag2 - bg - c
b' = -2ag - b
c' = -a
We see in each of these cases that a',b', and c' are integers.
(4) Let D = the discriminant = b2 - 4ac
(5) Let r = √D so that:
α = (-b + r)/2a
α = (-b - r)/2a
(6) From #2 and #3, we have:
α' = 1/(α - g) = 1/[(r-b)/2a - g] = 1/[(r - b - 2ag)/2a] = 2a/(r - b - 2ag) = 2a/(r + b')
(7) We can continue working with 2a/(r + b') to get:
2a/(r + b') = [2a(r - b')]/(r2 - b'2)
(8) r2 - b'2 = b2 - 4ac - (-2ag - b)2 =
= b2 - 4ac - 4a2g2 - 4abg - b2 =
= 2a(-2c - 2ag2 -2bg) =
= (2a)(2)(-c + -ag2 - bg) = (2a)(2a')
(9) Combining #7 and #8 gives us:
α' = 2a/(r + b') = (r - b')/(2a')
(10) Further, we note that:
b'2 - 4a'c' = (-2ag - b)2 - 4(-ag2 - bg - c)(-a) =
= 4a2g2 + 4abg + b2 -4a2g2 - 4abg - 4ac = b2 - 4ac
(11) So that r = √b2 - 4ac = √b'2 - 4a'c'
(12) Putting together #9 and #11, gives us:
α' = [-b' + √b'2 - 4a'c']/(2a')
(13) And this is a solution to a quadratic equation (see here) which gives us:
a'α2 + b'α' + c' = 0.
(14) We know that α' is a positive, improper fraction since:
α' = 1/(α - g) and α - g is less than 1.
(15) Further, we can use the same reasoning to establish that:
α' = 1/(α - g) is the second solution to the same equation since:
α = (-b-r)/2a
1/(α - g) = 1/[(-b-r-2ag)/2a] = 2a/(-b -r -2ag) = 2a/(-r + b') = 2a(-r -b')/(r2 - b'2)
Combining the above with #8 gives:
α' = (-r -b')/2a'
(16) By the equation in #15, we can also see that:
α' is a negative proper fraction since g is an integer greater than 1.
QED
Lemma 3: If α is a reduced number, then its continued fraction representation is purely periodic.
(1) Let α be a reduced number. That is:
(a) α is a positive, improper fraction of an integral quadratic equation such that:
aα2 + bα + c = 0.
(b) α is the second root for the above equation and is a negative, proper fraction.
(c) The discriminant: D = b2 - 4ac and is not a square.
(2) α * α =
(b2 - b2 + 4ac)/4a2 = c/a
(3) α + α =
= -2b/2a = -b/a
(4) From #2 and #3, we can assume that c,b are negative and a is positive.
We know that product is negative and we know that the addition is positive since α is greater than α
(5) For a continued fraction, we know that:
α = g + 1/α'
We know that g is the greatest integer less than α.
We also know that α' is itself a reduced number.
(6) From lemma 2, we also know that:
α' = 1/(α - g)
1/α' = α - g
-1/α' = g - α
(7) As shown in Lemma 2, each reduced number in the continued fraction representation corresponds to the same discriminant D (see Lemma 2 above)
(8) The number of different reduced numbers that correspond to a given discriminant D is finite since:
(a) -ac is greater than 0 since a is positive and c is negative.
(b) We know that b is negative so that b can only take value -1, -2, ... -r since b2 - 4ac must equal D.
(c) Additionally since D is nonsquare, we know that ac ≥ 1 and we know that b2 must then be divisible by 4.
(d) From (c), we know that -ac = (D - b2)/4 which in turn gives us a finite amount of numbers a,c since for each (D - b2)/4 value there are only so many integers than when multiplied are equal to this result: a can take value from 1 thru (D - b2)/4 and c can take a value from -1 thru -(D - b2)/4 value.
(9) From #8, we know that there are a finite number of derived values (α') that can come up so eventually the continued fraction will repeat.
(10) So, let's assume that we have a pattern that repeats:
U = (K, L, u)
u = (h,k,l,u)
In the above case, u is the irrational number that repeats. K,L,h,k,l are integers.
(11) We know that the solution u is associated with a second root u
(12) Now, according to #6, we know that for the same second root, there must be the same previous floor value. So, we can conclude that L=l and K=k.
(13) In other words, all previous values of the continued fraction must match.
(14) The only way that this can work is if we are dealing with a purely periodic continued fraction.
Since, #13 is not true of a repeating continued fraction that is not a purely periodic continued fraction:
Consider √6 above, sometimes the value preceding the 2 is a 2 and sometimes it is a 4. In other words, it violates the assumption in #13.
On the other hand, this is true of a purely periodic continued fraction.
Consider √112 + 10/ 6 above, all integers will always have the same value beforehand the same value. It does not violate the assumption in #13.
QED
Theorem 1: An irrational number results in a purely periodic continued fraction if and only if it is a reduced number.
(1) All purely periodic continued fractions represent reduced numbers (Lemma 1)
(2) All reduced numbers result in purely periodic continued fractions (Lemma 3)
QED
For those not familiar with continued fractions, start here. For those who are not familiar with Pell's Equation, start here. For those not familiar with how Pell's Equation fits into Fermat's Last Theorem, see here.
Today's blog is based on Heinrich Dorrie's 100 Great Problems of Elementary Mathematics.
In a previous blog, I showed that a continued fraction is periodic if and only if it represents the root of a quadratic equation (see here).
A purely periodic continued fraction is a continued fraction where the entire fraction a0 through an repeats. Here are some examples:
(a) This continued fraction is periodic but not purely periodic.
√6 = [ 2, 2, 4 ] (see here)
(b) This continued fraction is purely periodic.
√112 + 10/ 6 = [ 3, 2, 3, 10 ]
Just as periodic continued fractions correspond to quadratic equations, it turns out that purely periodic continued fractions correspond to what we will call "reduced" quadratic equations.
Definition: A reduced quadratic equation is any quadratic equation where the first root is a positive irrational greater than 1, its second root is a negative irrational that is greater than -1 and less than 0, and the discriminant is a nonsquare integer.
The discriminant refers to D in the following equation (see here):
x = (-b ± √d)/2a =(-b ± √b2 - 4ac)/2a
So the discriminant D is always equal to: b2 - 4ac.
In other words, the first root is a positive improper fraction (a fraction whose numerator is larger than or equal to its denominator such as 11/4 or 3/3) and the second root is a negative proper fraction (a fraction whose numerator is less than its denominator such as 1/2 or 1/3).
In my next blog, I will show how purely periodic continued fractions can be used to solve Pell's Equation.
Lemma 1: Every purely periodic continued fraction is a representation of a reduced quadratic equation.
(1) Let α be the purely periodic continued fraction with period n:
α = [ a1, a2, ...., an, a1, ... ]
(2) Let N be an even multiple of n such that we have:
α = [ a1, a2,, ..., aN, α ]
(3) We can assume that a1, a2, ... are integers greater than 0. [See here]
(4) Let P/Q be the Nth approximation of this continued fraction such that:
P/Q = [ a1, a2, ..., aN ]
(5) Let p/q be the (N-1)th approximation of this continued fraction such that:
p/q = [ a1, a2, ..., aN-1 ]
(6) According to previous results:
(a) Pq - Qp = 1 (see Lemma 2 here)
(b) α = (Pα + p)/(Qα + q) (see Lemma 1 here)
(c) α lies in between P/Q and p/q. It is greater than one and less than the other. (see Corollary 5.2 here )
(7) Rearranging (6b) gives us:
Qα2 + qα - Pα - p = 0.
(8) If we set H = P - q, we get:
Qα2 - Hα - p = 0.
(9) Solving for α gives us two roots such that:
α = H ± √H2 + 4Qp/(2Q)
(10) The discriminant D = H2 + 4Qp (see definition above) which means:
D = H2 + 4Pq - 4 = (P + q)2 - 4.
This shows that D is not a square (see here for proof )
(11) Let r = √D
(12) If we set α as the first root and α as the second root, we see that:
α = (H + r)/2Q
α = (H - r)/2Q
(13) We also note that r is greater than H since r = H2 + 4Qp and 4Qp ≥ 4 (see here)
(14) So we know that α is positive and that α is negative (since r,Q are ≥ 1; Q is greater than 1 by above)
(15) We know that α is an improper fraction since in order for it to repeat, it needs to be equal to the reciprocal of a proper fraction (that is, 1/[α - floor(α)] ) so that all we have left is to prove that α is a proper fraction.
(16) α * α = (H+r)(H-r)/[(2Q)(2Q)] = H2 - r2/4Q2 =
=( H2 - [H2 + 4Qp])/4Q2 =
-4Qp/4Q2 = -p/Q
(17) So α = (p/Q)/α
(18) Since P is greater than p (see Corollary 4.2, here), Q is greater than q (see Lemma 4 here), we have:
- α is less than (P/Q)/α and less than (p/q)/α
(19) But since α lies between P/Q and p/q (see #6c above), we know that one value is greater than α and one value is less than α.
(20) A value less over α is a proper fraction and we have shown that - α lies between 0 and a proper fraction. So, therefore, it must be a proper fraction.
(21) We have thus proven that α is a reduced number -- that is, it is the root a reduced equation (see definition above)
QED
Lemma 2: All irrational numbers that result from the continued fraction expansion of a reduced number are themselves solutions to a quadratic equation.
(1) Let α be a reduced number.
That is, it is an improper fraction solution to:
ax2 + bx + c = 0
Where: a,b,c are relatively prime integers and α is a negative proper fraction.
(2) For the start of the expansion, we note that:
α' = 1/(α - g)
That is: g is the largest whole number less than α and α' is the first derivative from α. In this case, g corresponds to a0 of the continued fraction.
(3) Let's also define a', b', c' such that:
a' = -ag2 - bg - c
b' = -2ag - b
c' = -a
We see in each of these cases that a',b', and c' are integers.
(4) Let D = the discriminant = b2 - 4ac
(5) Let r = √D so that:
α = (-b + r)/2a
α = (-b - r)/2a
(6) From #2 and #3, we have:
α' = 1/(α - g) = 1/[(r-b)/2a - g] = 1/[(r - b - 2ag)/2a] = 2a/(r - b - 2ag) = 2a/(r + b')
(7) We can continue working with 2a/(r + b') to get:
2a/(r + b') = [2a(r - b')]/(r2 - b'2)
(8) r2 - b'2 = b2 - 4ac - (-2ag - b)2 =
= b2 - 4ac - 4a2g2 - 4abg - b2 =
= 2a(-2c - 2ag2 -2bg) =
= (2a)(2)(-c + -ag2 - bg) = (2a)(2a')
(9) Combining #7 and #8 gives us:
α' = 2a/(r + b') = (r - b')/(2a')
(10) Further, we note that:
b'2 - 4a'c' = (-2ag - b)2 - 4(-ag2 - bg - c)(-a) =
= 4a2g2 + 4abg + b2 -4a2g2 - 4abg - 4ac = b2 - 4ac
(11) So that r = √b2 - 4ac = √b'2 - 4a'c'
(12) Putting together #9 and #11, gives us:
α' = [-b' + √b'2 - 4a'c']/(2a')
(13) And this is a solution to a quadratic equation (see here) which gives us:
a'α2 + b'α' + c' = 0.
(14) We know that α' is a positive, improper fraction since:
α' = 1/(α - g) and α - g is less than 1.
(15) Further, we can use the same reasoning to establish that:
α' = 1/(α - g) is the second solution to the same equation since:
α = (-b-r)/2a
1/(α - g) = 1/[(-b-r-2ag)/2a] = 2a/(-b -r -2ag) = 2a/(-r + b') = 2a(-r -b')/(r2 - b'2)
Combining the above with #8 gives:
α' = (-r -b')/2a'
(16) By the equation in #15, we can also see that:
α' is a negative proper fraction since g is an integer greater than 1.
QED
Lemma 3: If α is a reduced number, then its continued fraction representation is purely periodic.
(1) Let α be a reduced number. That is:
(a) α is a positive, improper fraction of an integral quadratic equation such that:
aα2 + bα + c = 0.
(b) α is the second root for the above equation and is a negative, proper fraction.
(c) The discriminant: D = b2 - 4ac and is not a square.
(2) α * α =
(b2 - b2 + 4ac)/4a2 = c/a
(3) α + α =
= -2b/2a = -b/a
(4) From #2 and #3, we can assume that c,b are negative and a is positive.
We know that product is negative and we know that the addition is positive since α is greater than α
(5) For a continued fraction, we know that:
α = g + 1/α'
We know that g is the greatest integer less than α.
We also know that α' is itself a reduced number.
(6) From lemma 2, we also know that:
α' = 1/(α - g)
1/α' = α - g
-1/α' = g - α
(7) As shown in Lemma 2, each reduced number in the continued fraction representation corresponds to the same discriminant D (see Lemma 2 above)
(8) The number of different reduced numbers that correspond to a given discriminant D is finite since:
(a) -ac is greater than 0 since a is positive and c is negative.
(b) We know that b is negative so that b can only take value -1, -2, ... -r since b2 - 4ac must equal D.
(c) Additionally since D is nonsquare, we know that ac ≥ 1 and we know that b2 must then be divisible by 4.
(d) From (c), we know that -ac = (D - b2)/4 which in turn gives us a finite amount of numbers a,c since for each (D - b2)/4 value there are only so many integers than when multiplied are equal to this result: a can take value from 1 thru (D - b2)/4 and c can take a value from -1 thru -(D - b2)/4 value.
(9) From #8, we know that there are a finite number of derived values (α') that can come up so eventually the continued fraction will repeat.
(10) So, let's assume that we have a pattern that repeats:
U = (K, L, u)
u = (h,k,l,u)
In the above case, u is the irrational number that repeats. K,L,h,k,l are integers.
(11) We know that the solution u is associated with a second root u
(12) Now, according to #6, we know that for the same second root, there must be the same previous floor value. So, we can conclude that L=l and K=k.
(13) In other words, all previous values of the continued fraction must match.
(14) The only way that this can work is if we are dealing with a purely periodic continued fraction.
Since, #13 is not true of a repeating continued fraction that is not a purely periodic continued fraction:
Consider √6 above, sometimes the value preceding the 2 is a 2 and sometimes it is a 4. In other words, it violates the assumption in #13.
On the other hand, this is true of a purely periodic continued fraction.
Consider √112 + 10/ 6 above, all integers will always have the same value beforehand the same value. It does not violate the assumption in #13.
QED
Theorem 1: An irrational number results in a purely periodic continued fraction if and only if it is a reduced number.
(1) All purely periodic continued fractions represent reduced numbers (Lemma 1)
(2) All reduced numbers result in purely periodic continued fractions (Lemma 3)
QED
Subscribe to:
Posts (Atom)
