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

6 comments:

Scouse Rob said...

In the link of step (2) of Theorem 2

It is proven that if D is of the form 4n or 4n+1 then a reduced quadratic equation that has a discriminant = D exists.

What about the cases when D=4n+2 or D=4n+3?

I'm tired and cannot work it out.

I'll have to wait here until tomorrow.

Any help in understanding this would be greatly appreciated.

Thanks

Rob

Scouse Rob said...

Good morning Larry.

A new day and a new outlook.

It seems so clearer now.

D=b^2-4ac≡b^2 mod 4.

If b is even then D≡0 mod 4 and D=4n.

If b is odd then D≡1 mod 4 and D=4n+1.

I'm sorry if I have been sending you too many comments over the last few days.

I truly think your blog is the greatest thing I have found on the internet (after online poker and, perhaps, metamath.)

Thank you for taking the time and the effort of posting all these wonderful proofs, and for working out the details to arrange them into easy to follow step by step proofs.

Rob

Scouse Rob said...

Larry

I'm sorry I still don't understand Theorem 2.


We know that there exists a reduced quadratic equation that has a discriminant=D

D has to be non-square to be a discriminant?

D also has to be equal to 1 or 0 mod 4?

Does this not restrict the statement of the Theorem to certain values of d.

I am confused.

Any help at all with this issue would be appreciated.

Rob

Scouse Rob said...

In step (4) of Theorem 2

(x-by)/2*(x+by)/2-(ay)(-cy)= x^2-b^2y^2+acy^2

should be

(x-by)/2*(x+by)/2-(ay)(-cy)= (x^2-b^2y^2)/4+acy^2

Rob

Scouse Rob said...

In step (11a) of Theorem 2

From #6, we know that..

should be

From #3, we know that

Scouse Rob said...

In step (11g) of Theorem 2


This gives us Q-q is greater than
-2(2+3)=-2(5)=-0.4.

should be

This gives us Q-q is greater than
-2/(2+3)=-2/(5)=-0.4.