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.
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]
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
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.
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
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.
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.