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 whose length is $s$:
- $\sqrt n = \sqbrk {a_1 \sequence {a_2, a_3, \ldots, a_{s + 1} } }$
Let $a_n = \dfrac {p_n} {q_n}$ be a convergent of $\sqrt n$.
Then:
- ${p_{r s} }^2 - n {q_{r s} }^2 = \paren {-1}^{r s}$ 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:
- $\sqbrk {a \sequence {b_1, b_2, \ldots, b_{m - 1}, b_m, b_{m - 1}, \ldots, b_2, b_1, 2 a} }$
or
- $\sqbrk {a \sequence {b_1, b_2, \ldots, b_{m - 1}, b_m, b_m, b_{m - 1}, \ldots, b_2, b_1, 2 a} }$
For each $r \ge 1$ we can write $\sqrt n$ as the (non-simple) finite continued fraction:
- $\sqrt n = \sqbrk {a \sequence {b_1, b_2, \ldots, b_2, b_1, 2 a, b_1, b_2, \ldots, b_2, b_1, x} }$
which has a total of $r s + 1$ partial denominators.
The last element $x$ is of course not an integer.
What we do have, though, is:
\(\ds x\) | \(=\) | \(\ds \sqbrk {\sequence {2 a, b_1, b_2, \ldots, b_2, b_1} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds a + \sqbrk {a, \sequence {b_1, b_2, \ldots, b_2, b_1, 2 a} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds a + \sqrt n\) |
The final three convergents in the above FCF are:
- $\dfrac {p_{r s - 1} } {q_{r s - 1} }, \quad \dfrac {p_{r s} } {q_{r s} }, \quad \dfrac {x p_{r s} + p_{r s - 1} } {x q_{r s} + q_{r s - 1} }$
The last one of these equals $\sqrt n$ itself.
So:
- $\sqrt n \paren {x q_{r s} + q_{r s - 1} } = \paren {x p_{r s} + p_{r s - 1} }$
Substituting $a + \sqrt n$ for $x$, we get:
- $\sqrt n \paren {\paren {a + \sqrt n} q_{r s} + q_{r s - 1} } = \paren {\paren {a + \sqrt n} p_{r s} + p_{r s - 1} }$
This simplifies to:
- $\sqrt n \paren {a q_{r s} + q_{r s - 1} - p_{r s} } = a p_{r s} + p_{r s - 1} - n q_{r s}$
The right hand side of this is an integer while the left hand side 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:
\(\text {(1)}: \quad\) | \(\ds a q_{r s} + q_{r s - 1}\) | \(=\) | \(\ds p_{r s}\) | |||||||||||
\(\text {(2)}: \quad\) | \(\ds a p_{r s} + p_{r s - 1}\) | \(=\) | \(\ds n q_{r s}\) |
Multiplying $(1)$ by $p_{r s}$, $(2)$ by $q_{r s}$ and then subtracting:
- $p_{r s}^2 - n q_{r s}^2 = p_{r s} q_{r s - 1} - p_{r s - 1} q_{r s}$
By Difference between Adjacent Convergents of Simple Continued Fraction, the right hand side of this is $\paren {-1}^{r s}$.
When the cycle length $s$ of the continued fraction of $\sqrt n$ is even, we have $\paren {-1}^{r s} = 1$.
Hence $x = p_{r s}, y = q_{r s}$ is a solution to Pell's Equation for each $r \ge 1$.
When $s$ is odd, though:
- $x = p_{r s}, y = q_{r s}$ is a solution of $x^2 - n y^2 = -1$ when $r$ is odd
- $x = p_{r s}, y = q_{r s}$ is a solution of $x^2 - n y^2 = 1$ when $r$ is even.
$\blacksquare$
Sequence
The minimum solutions of $x$ and $y$ for the Diophantine equation $x^2 - n y^2 = 1$ for various values of $n$ are as follows:
$n$ $x$ $y$ $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$
Note the unusual peak at $13$.
Thus, the sequence for $x$ for non-square $n$ begins:
- $3, 2, 9, 5, 8, 3, 19, 10, 7, 649, 15, 4, 33, 17, 170, \ldots$
Similarly, the sequence for $y$ for non-square $n$ begins:
- $2, 1, 4, 2, 3, 1, 6, 3, 2, 180, 4, 1, 8, 4, 39, 2, 12, \ldots$
Examples
Pell's equation: $x^2 - 2 y^2 = 1$
- $x^2 - 2 y^2 = 1$
has the positive integral solutions:
- $\begin {array} {r|r} x & y \\ \hline
3 & 2 \\ 17 & 12 \\ 99 & 70 \\ 577 & 408 \\ 3363 & 2378 \\ \end {array}$
and so on.
Pell's equation: $x^2 - 2 y^2 = -1$
- $x^2 - 2 y^2 = -1$
has the positive integral solutions:
- $\begin {array} {r|r} x & y \\ \hline
1 & 1 \\ 7 & 5 \\ 41 & 29 \\ 239 & 169 \\ 1393 & 985 \\ \end {array}$
and so on.
Pell's equation: $x^2 - 8 y^2 = 1$
- $x^2 - 8 y^2 = 1$
has the positive integral solutions:
\(\ds \tuple {x, y}\) | \(=\) | \(\ds \tuple {3, 1}\) | ||||||||||||
\(\ds \tuple {x, y}\) | \(=\) | \(\ds \tuple {17, 6}\) | ||||||||||||
\(\ds \tuple {x, y}\) | \(=\) | \(\ds \tuple {99, 35}\) | ||||||||||||
\(\ds \tuple {x, y}\) | \(=\) | \(\ds \tuple {577, 204}\) | ||||||||||||
\(\ds \tuple {x, y}\) | \(=\) | \(\ds \tuple {3363, 1189}\) |
and so on.
Pell's equation: $x^2 - 13 y^2 = 1$
- $x^2 - 13 y^2 = 1$
has the smallest positive integral solution:
- $x = 649$
- $y = 180$
Pell's equation: $x^2 - 29 y^2 = 1$
- $x^2 - 29 y^2 = 1$
has the smallest positive integral solution:
- $x = 9801$
- $y = 1820$
Pell's equation: $x^2 - 61 y^2 = 1$
- $x^2 - 61 y^2 = 1$
has the smallest positive integral solution:
- $x = 1 \, 766 \, 319 \, 049$
- $y = 226 \, 153 \, 980$
Also defined as
Some sources define Pell's equation as:
- $x^2 - n y^2 = \pm m$
on the understanding that $m$ is usually taken to be $1$.
Some sources also specify that $n$ should be square-free.
Also known as
A particular instance of Pell's equation can also be seen referred to as a Pellian equation.
Source of Name
This entry was named for John Pell.
Historical Note
It is popularly believed that Pell's Equation was misattributed to John Pell by Euler, and that it was in fact William Brouncker who was the first European to solve it.
However, Pell's Equation appears in Teutsche Algebra by Johann Heinrich Rahn ($1659$), which was certainly written with Pell's help, and possibly written entirely by Pell.
Some sources attribute Pell's Equation to Pierre de Fermat.
Pell's Equation had been extensively investigated by Brahmagupta and subsequent mathematicians of the Indian tradition as far back as $628$ C.E.
Subsequently Bhaskara II in the $12$th century and Narayana Pandit in the $14$th found solutions.
Sources
- 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $1 \cdotp 41421 \, 35623 \, 73095 \, 04880 \, 16887 \, 24209 \, 69807 \, 85697 \ldots$
- 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $4,729,494$
- 1989: Ephraim J. Borowski and Jonathan M. Borwein: Dictionary of Mathematics ... (previous) ... (next): Pell's equation
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $1 \cdotp 41421 \, 35623 \, 73095 \, 04880 \, 16887 \, 24209 \, 69807 \, 85697 \ldots$
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $13$
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $4,729,494$
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): Pell's equation
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Pell's equation
- 2008: Ian Stewart: Taming the Infinite ... (previous) ... (next): Chapter $7$: Patterns in Numbers: Fermat
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Pell's equation
- 2021: Richard Earl and James Nicholson: The Concise Oxford Dictionary of Mathematics (6th ed.) ... (previous) ... (next): Pell's equation
- Weisstein, Eric W. "Pell Equation." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PellEquation.html