Suppose that d and N are fixed integers. The equation
x2 dy2 = 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 -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)2 d = 1/y2.
If we factor the left side, we get
((x/y) )((x/y) + ) = 1/y2,
which implies that
(x/y) = 1/(y2((x/y) + )).
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 . Therefore a solution to Pell's equation will give us a good rational approximation to .
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 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 , which we denote by pk/qk, and then computes
The output is a list of the terms of the form ((pk, qk), pk2 dqk2). 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:
The very first term shows us that (9, 4) is a solution to x2 5y2 = 1. Let's double check it:
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.
This time we found two solutions, (8, 3) and (127, 48). Now it's your turn.
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 x2 dy2 = 1 arises as the numerator and denominator of a convergent from the continued fraction expansion of . (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 , narrow down the possibilities as to which convergents yield solutions to x2 dy2 = 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.)
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