Suppose that

dandNare fixed integers. The equationx^{2}–dy^{2}=Nis 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 andd> 0. Ify= 0, then Pell's equation is simplyx^{2}=N, which is not very interesting. Hence we will look for solutions to Pell's equation in positive integersxandy. Suppose that we had such a solution. Then we can divide byy^{2}to obtain( x/y)^{2}–d= 1/y^{2}.If we factor the left side, we get

(( x/y) – )((x/y) + ) = 1/y^{2},which implies that

( x/y) – = 1/(y^{2}((x/y) + )).Note that the right-hand side of the last expression above will be small, especially if

yis large. Hence the left-hand side must also be small, which implies thatx/yis 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

xbe the numerator andybe 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 boundBthat specifies the number of convergents to be tested. The function takes thekth convergent for the continued fraction expansion of , which we denote byp/_{k}q, and then computes_{k}p_{k}^{2}–dq_{k}^{2}.The output is a list of the terms of the form ((

p,_{k}q),_{k}p_{k}^{2}–dq_{k}^{2}). Those terms with second entry equal to 1 indicate solutions to Pell's equation. Here's what we get ford= 5 andB= 10:The very first term shows us that (9, 4) is a solution to

x^{2}– 5y^{2}= 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

x^{2}– 7y^{2}= 1.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)x^{2}– 19y^{2}= 1.

(b)x^{2}– 46y^{2}= 1.

(c)x^{2}– 61y^{2}= 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

dis not a perfect square, then every solution (x,y) ofx^{2}–dy^{2}= 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

x^{2}–dy^{2}= 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

Copyright © 2001 by W. H. Freeman and Company