Suppose that d and N are fixed integers. The equation
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
If we factor the left side, we get
)((x/y) + ) =
1/y2,
which implies that
=
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.
Exercise 4Find the smallest solution in positive integers to:
(a) x2 – 19y2 = 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 |