Pell's Equation

From ProofWiki
Jump to: navigation, search

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 quotients.

The last element $x$ is of course not an integer.


What we do have, though, is:

\(\displaystyle x\) \(=\) \(\displaystyle \sqbrk {\sequence {2 a, b_1, b_2, \ldots, b_2, b_1} }\)
\(\displaystyle \) \(=\) \(\displaystyle a + \sqbrk {a, \sequence {b_1, b_2, \ldots, b_2, b_1, 2 a} }\)
\(\displaystyle \) \(=\) \(\displaystyle 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:

\((1):\quad\) \(\displaystyle a q_{r s} + q_{r s - 1}\) \(=\) \(\displaystyle p_{r s}\)
\((2):\quad\) \(\displaystyle a p_{r s} + p_{r s - 1}\) \(=\) \(\displaystyle 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$

This sequence is A033313 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).


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$

This sequence is A033317 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).


Examples

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 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, the 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.

Pell's 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 $12$th century and Narayana Pandit in the $14$th found solutions.


Sources