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: [a₀, a₁, ..., a_n-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: [ a₀, a₁, a₂, ..., a_n-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) au² + bu + c = 0, gcd(a,b,c)=1, a,b,c are integers
(b) a'u² + 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 = au² + 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 x² - dy² = 4

(1) Let [ a₁, a₂, ... a_n, a₁, ... a_n ] be the representation of a reduced quadratic equation au² + 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 = [ a₁, ... a_n ... a_N ]

(4) Let p/q = [ a₁, ... a_n ... a_N-1 ]

(5) From a previous result and (1) we know that;
u = (Pu + p)/(Qu + q) [see here]

So that:
Qu² + qu - Pu - p = 0

(6) Let H = P - q

(7) We then have the following form for (5)
Qu² - 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:
x² - b²y² = (P + q)² - (P-q)²

(12) From (8):
4acy² = 4ac(Q/a)(p/-c) = -4Qp

(13) Since D = b² - 4ac, we have:
x² - dy² = x² - Dy² =
= x² - (b² - 4ac)y² =
= x² - b²y² + 4acy²

(14) Combining (13) with (11) and (12) gives us:
x² - dy² = (P + q)² - (P - q)² - 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:
x² - dy² = 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: x² - dy² = 1.

(2) Let x' = 2x, d' = 4d.

(3) Use the above theorem to solve:
(x')² - (d')y² = 4

This means that:
(2x)² - (4d)y² =4x² - 4dy² = 4

Which dividing all sides by 4 implies:
x² - dy² = 1.

QED

Theorem 2: Every solution to the equation x² - dy² = 4 is solved by the method in Thereom 1.

(1) Let x, y be a solution to x² - dy² = 4.

(2) We know that there exists a reduced quadratic equation that has a discriminant = D (see here for proof) such that:

au² + 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) = [x² - b²y²]/4 + acy² =
= [x² - b²y² + 4acy²]/4 =
= [x² - (b² - 4ac)y²]/4 =
= [x² - dy²]/4

(5) Now applying #1 to #4 gives us:

Pq - Qp = [x² - dy²]/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)u² + [-(P-q)/y]u + -p/y = 0

(8) Multiplying all sides by y gives us:

Qu² -Pu + qu -p = 0

(9) Which implies:

Qu² + 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 r² = d (see here for definition of discriminant) and using #1, we get:
r²y² - x² = -1(x² - dy²) = -4

(d) So:
2(Q -q) is greater than ry - x = (r²y² - x²)/(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 = [ a₁, a₂, ..., a_n ]

(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:
[ a₁, ..., a_n, u ] = (Pu + p)/(Qu + q) [ See here for proof ]

(19) Apply #10 gives us;
u = [ a₁, ..., a_n, 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 x² - 112y² = 4.

(1) We first find a reduced quadratic equation where the discriminant = 112. Let's use:
3u² - 10u - 1 = 0.

D = b² - 4ac = (-10)² - 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):

p₁ = 3
p₂ = 7
p₃ = 24
p₄ = 247

q₁ = 1
q₂ = 2
q₃ = 7
q₄ = 72

x = P + q = 247 + 7 = 254
y = Q/a = 72/3 = 24.

(254)² - 112(24)² = 64,516 - 112(576) = 64,516 - 64,512 = 4.

QED