Pell's Equation

From ProofWiki
Jump to navigation Jump to 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 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

Retrieved from "https://proofwiki.org/w/index.php?title=Pell%27s_Equation&oldid=670418"