13.4   "Pell's Equation"

Suppose that d and N are fixed integers. The equation

x2dy2 = N

is known as Pell's Equation, and is named after John Pell, a mathematician who searched for integer solutions to equations of this type in the seventeenth century. Ironically, Pell was not the first to work on this problem, nor did he contribute to our knowledge for solving it. Euler, who brought us the phi-function, accidentally named the equation after Pell, and the name stuck.

In this section we will concentrate on solutions to Pell's equation for the case where N = 1 and d > 0. If y = 0, then Pell's equation is simply x2 = N, which is not very interesting. Hence we will look for solutions to Pell's equation in positive integers x and y. Suppose that we had such a solution. Then we can divide by y2 to obtain

(x/y)2d = 1/y2.

If we factor the left side, we get

((x/y) – sqrt(d))((x/y) + sqrt(d)) = 1/y2,

which implies that

(x/y) – sqrt(d) = 1/(y2((x/y) + sqrt(d))).

Note that the right-hand side of the last expression above will be small, especially if y is large. Hence the left-hand side must also be small, which implies that x/y is close in value to sqrt(d). Therefore a solution to Pell's equation will give us a good rational approximation to sqrt(d).

In view of the preceding observations, it is natural to try to reverse the process and search for solutions to Pell's equation by looking among the rational approximations to sqrt(d) generated from the continued fraction expansion. We will let x be the numerator and y be the denominator of a convergent, and check to see if we have a solution to our equation.

The applet below lets you input a value for d, and a bound B that specifies the number of convergents to be tested. The function takes the kth convergent for the continued fraction expansion of sqrt(d), which we denote by pk/qk, and then computes


The output is a list of the terms of the form ((pk, qk), pk2dqk2). Those terms with second entry equal to 1 indicate solutions to Pell's equation. Here's what we get for d = 5 and B = 10:

Your browser does not support java.

The very first term shows us that (9, 4) is a solution to x2 – 5y2 = 1. Let's double check it:

Your browser does not support java.

There are several other solutions as well: (161, 72), (2889, 1292), (51841, 23184), and (930249, 416020). Let's try another example, say x2 – 7y2 = 1.

Your browser does not support java.

This time we found two solutions, (8, 3) and (127, 48). Now it's your turn.

Exercise 4

Find the smallest solution in positive integers to:

(a) x2 – 19y2 = 1.
(b) x2 – 46y2 = 1.
(c) x2 – 61y2 = 1.

In each of the examples we have considered, it's clear that we could examine more convergents with the hope of finding more solutions. Remarkably, it turns out that if d is not a perfect square, then every solution (x, y) of x2dy2 = 1 arises as the numerator and denominator of a convergent from the continued fraction expansion of sqrt(d). (You do not need to prove this assertion.) The question for you to consider is, which convergents should we use? Narrowing down the possibilities is the subject of the next Research Question. You may find the applets provided below helpful in conducting your search for a pattern.

Research Question 2

On the basis of the continued fraction expansion of sqrt(d), narrow down the possibilities as to which convergents yield solutions to x2dy2 = 1.

(Again, focus on formulating a good conjecture. A proof is not reasonably accessible with the knowledge we have developed of continued fractions thus far.)

Your browser does not support java.

Your browser does not support java.

Section 13.1 | Section 13.2 | Section 13.3 | Section 13.4

Chapter 13 | DNT Table of Contents

Copyright © 2001 by W. H. Freeman and Company