nx²+1=y² is known as Pell's equation, where n is a positive integer which is not a perfect square, and (x,y) are integers that solve the equation.

Solving Pell's Equation

Identity 1

To aid in solving y²-nx²=1, the following identity is helpful:

(b² - na²)(d² - nc²) = (bd ± nac)² - n(bc ± ad)²

From this we see that if b²-na² and d²-nc² are both 1 then

(bd ± nac)² - n(bc ± ad)² = 1

In other words, if (a,b) and (c,d) are solutions to Pell's equation then so are (bc ± ad, bd ± nac)

Brahmagupta's Lemma, a.k.a. The Method of Composition

If (a, b) and (c, d) are integer solutions of "Pell type equations" of the form

na² + k = b² and nc² + k' = d²

then (bc ± ad, bd ± nac) are both integer solutions of the "Pell type equation" 

nx² + kk' = y².

Using the Method of Composition, if (a,b) satisfies Pell's equation, then so does (2ab, b²+na²), which is obtained by composing (a,b) with itself.  Additional solutions can be obtained by composing (a,b) with (2ab, b²+na²), etc.

Solving Pell Equations using Brahmagupta's Method

From Brahmagupta's Lemma, if (a,b) is a solution to nx² + k = y², then composing (a,b) with itself gives you

(2ab, b²+na²) as a solution to nx² + k² = y², and thus also to n(x/k)² + 1 = (y/k)², so

x=2ab/k, y=(b²+na²)/k is a solution to the Pell Equation nx² + 1 = y²

For most values of k this isn't helpful, because x and y aren't integers, but when k is ±1, ±2, or, with a little more work, ±4, this idea helps a whole lot.

When k=2,  Since (a,b) is a solution to nx² + k = y², we know that

na² = b²-2, so x=2ab/2=ab, y=(b²+b²-2)/2=b²-1

(ab, b²-1) is a solution to the related Pell Equation nx² + 1 = y².

Here's an example: solve 23x²+1=y².

Start by observing that a solution to the related Pell type equation 23x²+2=y² is (1,5), so (5,24) is a solution to 23x²+1=y².

When k=-2,  Since (a,b) is a solution to nx² + k = y², we know that

na² = b²+2, so x=2ab/-2=-ab, y=-(b²+b²+2)/-2=-b²-1

(-ab, -b²-1) is a solution to the related Pell Equation nx² + 1 = y², and so
(ab, b²+1) is also a solution.

Here's an example: solve 83x²+1=y².

Start by observing that a solution to the related Pell type equation 83x²-2=y² is (1,9), so (9,82) is a solution to 83x²+1=y².

Cyclic Method

Observe that a solution to nx² + (m²-n) = y² is (1,m).
e.g. a solution to 7x² + 2 = y² is (1,3) because 2=3²-7

Now, suppose we are looking for a solution to nx² + 1 = y², and we can find a "close" pair (a,b) that solves nx² + k = y².  In other words, na² + k = b².

Now, compose (1,m) and (a,b) to see that (am+b, bm+na) is a solution to nx² + (m²-n)k = y²; in other words,
n(am+b)² + (m²-n)k = (bm+na)².

Dividing by k, we see that ((am+b)/k, (bm+na)/k) solves nx²+(m²-n)/k = y².

 . . . . continue reading The history of Pell's Equation, . . . .

Other Notes

Here are random factoids culled from websites, which may or may not be important:

The first non-trivial solution of this Diophantine equation, from which all others are easily computed, can be found using, e.g., the cyclic method [1], known in India in the 12th century, or using the slightly less efficient but more regular English method [1] (17th century). There are other methods to compute this so-called fundamental solution, some of which are based on a continued fraction expansion of the square root of A.

Internet References

The history of Pell's Equation, which apparently was misattributed to Pell by Euler, and actually studied first 1000 years before Pell's time by Brahmagupta.

Large fundamental solutions of Pell's equation, in which A's are found that result in very large solutions to Ax^2+1=y^2

Related Pages in this website

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]