Pell's Equation

Definition

The Diophantine equation:

$x^2 - n y^2 = 1$

is known as Pell's equation.

Solution

Let the continued fraction of $\sqrt n$ have a cycle length $s$.

Let $\dfrac {p_n} {q_n}$ be a convergent of $\sqrt n$.

Then:

$p_{rs}^2 - n q_{rs}^2 = \left({-1}\right)^{rs}$ for $r = 1, 2, 3, \ldots$

and all solutions of:

$x^2 - n y^2 = \pm 1$

are given in this way.

Proof

First note that if $x = p, y = q$ is a positive solution of $x^2 - n y^2 = 1$ then $\dfrac p q$ is a convergent of $\sqrt n$.

The continued fraction of $\sqrt n$ is periodic from Continued Fraction Expansion of Irrational Square Root and of the form:

$\left[{a \left \langle{b_1, b_2, \ldots, b_{m-1}, b_m, b_{m-1}, \ldots, b_2, b_1, 2 a}\right \rangle}\right]$

or

$\left[{a \left \langle{b_1, b_2, \ldots, b_{m-1}, b_m, b_m, b_{m-1}, \ldots, b_2, b_1, 2 a}\right \rangle}\right]$

For each $r \ge 1$ we can write $\sqrt n$ as the (non-simple) finite continued fraction:

$\sqrt n \left[{a \left \langle{b_1, b_2, \ldots, b_2, b_1, 2 a, b_1, b_2, \ldots, b_2, b_1, x}\right \rangle}\right]$

which has a total of $rs + 1$ partial quotients. The last element $x$ is of course not an integer.

What we do have, though, is:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle x\)	\(=\)	\(\displaystyle \left[{\left \langle{2 a, b_1, b_2, \ldots, b_2, b_1}\right \rangle}\right]\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle a + \left[{a, \left \langle{b_1, b_2, \ldots, b_2, b_1, 2 a}\right \rangle}\right]\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle a + \sqrt n\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

The final three convergents in the above FCF are:

$\displaystyle \frac {p_{rs - 1}} {q_{rs - 1}}, \quad \frac {p_{rs}} {q_{rs}}, \quad \frac {x p_{rs} + p_{rs - 1}} {x q_{rs} + q_{rs - 1}}$

The last one of these equals $\sqrt n$ itself. So:

$\sqrt n \left({x q_{rs} + q_{rs - 1}}\right) = \left({x p_{rs} + p_{rs - 1}}\right)$

Substituting $a + \sqrt n$ for $x$, we get:

$\sqrt n \left({\left({a + \sqrt n}\right) q_{rs} + q_{rs - 1}}\right) = \left({\left({a + \sqrt n}\right) p_{rs} + p_{rs - 1}}\right)$

This simplifies to:

$\sqrt n \left({a q_{rs} + q_{rs - 1} - p_{rs}}\right) = a + p_{rs} + p_{rs - 1} - n q_{rs}$

The RHS of this is an integer while the LHS is $\sqrt n$ times an integer.

Since $\sqrt n$ is irrational, the only way that can happen is if both sides equal zero.

This gives us:

\((1):\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a q_{rs} + q_{rs - 1}\)	\(=\)	\(\displaystyle p_{rs}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\((2):\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a p_{rs} + p_{rs - 1}\)	\(=\)	\(\displaystyle n q_{rs}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Multiplying $(1)$ by $p_{rs}$, $(2)$ by $q_{rs}$ and then subtracting:

$p_{rs}^2 - n q_{rs}^2 = p_{rs} q_{rs - 1} = p_{rs - 1} q_{rs}$

By Properties of Convergents of Continued Fractions, the RHS of this is $\left({-1}\right)^{rs}$.

When the cycle length $s$ of the continued fraction of $\sqrt n$ is even, we have $\left({-1}\right)^{rs} = 1$.

Hence $x = p_{rs}, y = q_{rs}$ is a solution to Pell's Equation for each $r \ge 1$.

When $s$ is odd, though:

• $x = p_{rs}, y = q_{rs}$ is a solution of $x^2 - n y^2 = -1$ when $r$ is odd
• $x = p_{rs}, y = q_{rs}$ is a solution of $x^2 - n y^2 = 1$ when $r$ is even.

$\blacksquare$

Source of Name

This entry was named for John Pell.

It is popularly believed that this is a misattribution by Euler and that it was in fact William Brouncker who was the first European to solve it. However, the equation appears in Teutsche Algebra by Rahn (1659) which was certainly written with Pell's help, and possibly entirely written by Pell.

The equation had been extensively investigated by Brahmagupta and subsequent mathematicians of the Indian tradition as far back as 628 C.E.: subsequently Bhāskara II in the 12th century and Narayana Pandit in the 14th found solutions.