# Pell's Equation

Math Lair Home > Topics > Pell's Equation

The Diophantine equation x² − Ny² = 1, where N is a constant, is called Pell's equation, named after John Pell. Pell never actually worked on what is now called Pell's equation, but Euler thought he did, so there you go. Perhaps a better name for the equation might be "Brahmagupta's equation", after the Indian mathematician who studied the equation about a millennium before Pell didn't.

Some of the ancient Greeks may have worked on Pell's equation, but the first significant progress on the equation was made in India by Brahmagupta. In the 12th century, Bhaskara found a general solution to Pell's equation based on Brahmagupta's work. In the 17th century, European mathematicians rediscovered the equation, and in 1766 Lagrange proved that the equation always has a solution in natural numbers when N is not a square number (if N is a square number, solving the equation would require finding two squares that differ by 1; however, the only two such squares are 0 and 1, and 0 isn't a natural number).

The following illustrates how to solve Pell's equation, based on Bhaskara's method. For now, I've omitted proofs that the method works, but I may add this later. The method is called the Chakravala Method (also spelled Cakravâla method), also known as the Cyclic Method (if you're familiar with yoga and Eastern spirituality, you may know that "chakra" is Hindi for "circle" or "wheel"). This is a beautiful algorithm, perhaps one of the most beautiful discovered until relatively recently.

To solve the equation x² − Ny² = 1 (which we'll write as Ny² + 1 = x² from here on), Brahmagupta would first find an auxilliary equation Na² + k = b² where a, b, and k are small enough to be found by inspection and where the absolute value of k is not too big. For example, if you were trying to solve

60y² + 1 = x²
you might find the auxilliary equation
60 · 1² + 4 = 8²

Now, Brahmagupta would use what is called the Principle of Composition or Brahmagupta's Lemma to compose the auxilliary equation with another auxilliary equation or with itself. The principle of composition states that, if you have a1, b1, and k1 such that

Na1² + k1 = b1²
and a2, b2, and k2 such that
Na2² + k2 = b2²
then the following equation will also be true:
N(a1b2 ± a2b1)² + k1k2 = (b1b2 ± Na1a2

Now, if k = −1, ±2, or ±4, composing the auxilliary equation with itself will allow you to find a solution to the original equation right away. For solving 60y² + 1 = x² we found the auxilliary equation 60 · 1² + 4 = 8². Composing that with itself, we get:

60(1 · 8 + 1 · 8)² + 4 · 4 = (8 · 8 + 60 · 1 · 1)²
60(16)² + 16 = (124)²

Each term is a multiple of 16, so divide each term by 16:

60(4)² + 1 = (31)²

We now have a solution to the original equation: x = 31, y = 4. This is the smallest solution in natural numbers; to find other solutions, you can apply the principle of composition to the equation immediately above.

Now, this process can be hit-and-miss, and Brahmagupta wasn't able to use it to solve all such equations. However, Bhaskara's method allows us to find a solution all the time. Using Brahmagupta's Lemma, Bhaskara first showed that, if

Na² + k = b²
then it is also true that, for any m,
N(am + bk)² + m² − Nk = (bm + Nak

Choose m such that am + bk is an integer (in which case the other two fractions will be as well) and so that m² − N has the smallest absolute value possible. This will result in new auxilliary equation; if the new value of k is 1, you're done; otherwise, if it's −1, ±2, or ±4, you can use the Brahmagupta's method to find the solution; otherwise, repeat this process with the new equation,

Here's an example of the process for x² − 19y² = 1. Given this equation, one auxilliary equation we could form would be:

19(1)² + 6 = 5²

Now, we'll create the new auxilliary equation

19(1 · m + 56)² + m² − 196 = (5m + 19 · 16

Now, we need to find m such that 1 · m + 56 is an integer and |m² − 19| is as small as possible. By inspection, choose m = 1. Our auxilliary equation becomes:

19(1 · 1 + 56)² + 1² − 196 = (5 · 1 + 19 · 16
19(1)² − 3 = 4²

Now, create a new auxilliary equation as above. Find m such that 1 · m + 4−3 is an integer and |m² − 19| is as small as possible. A good choice is m = 5. This gives us the new auxilliary equation:

19(−3)² − 2 = (-13)²
19(3)² − 2 = 13²

Since the value of k in this equation is −2, we can compose this equation with itself, as in the previous example. This results in:

19(2(3)(13))² + 4 = (13² + 19 · 3²)
19(2 · 39)² + 4 = (340)²

Each term can be divided by 4, resulting in:

19(39)² + 1 = 170²

This gives us a solution: x = 170, y = 39.

The solutions to Pell's equation can sometimes be surprising; for example, the smallest solution in natural numbers for x² − 62y² = 1 is x = 63, y = 8; however, for x² − 61y² = 1 the smallest solutions are x = 1,766,319,049, y = 226,153,980. The smallest solutions in natural numbers for x² − Ny² = 1 for every value of N between 2 and 99 are listed in the table below; you'll notice a few other unusually large numbers there as well.
Nxy
2 3 2
3 2 1
5 9 4
6 5 2
7 8 3
8 3 1
10 19 6
11 10 3
12 7 2
13 649 180
14 15 4
15 4 1
17 33 8
18 17 4
19 170 39
20 9 2
21 55 12
22 197 42
23 24 5
24 5 1
26 51 10
27 26 5
28 127 24
29 9,801 1,820
30 11 2
31 1,520 273
32 17 3
33 23 4
34 35 6
35 6 1
37 73 12
38 37 6
39 25 4
40 19 3
41 2,049 320
42 13 2
43 3,482 531
44 199 30
45 161 24
46 24,335 3,588
47 48 7
48 7 1
50 99 14
51 50 7
52 649 90
53 66,249 9,100
54 485 66
55 89 12
56 15 2
57 151 20
58 19,603 2,574
59 530 69
60 31 4
61 1,766,319,049 226,153,980
62 63 8
63 8 1
65 129 16
66 65 8
67 48,842 5,967
68 33 4
69 7,775 936
70 251 30
71 3,480 413
72 17 2
73 2,281,249 267,000
74 3699 430
75 26 3
76 57,799 6,630
77 351 40
78 53 6
79 80 9
80 9 1
82 163 18
83 82 9
84 55 6
85 285,769 30,996
86 10,405 1,122
87 28 3
88 197 21
89 500,001 53,000
90 19 2
91 1,574 165
92 1,151 120
93 12,151 1,260
94 2,143,295 221,064
95 39 4
96 49 5
97 62,809,633 6,377,352
98 99 10
99 10 1

Sources used (see bibliography page for titles corresponding to numbers): 20.