Pell equation

A Pell equation is a type of diophantine equation in the form $x^2-Dy^2 = \pm1$ for a natural number $D$ . Generally, $D$ is taken to be square-free, since otherwise we can "absorb" the largest square factor $d^2 | D$ into $y$ by setting $y' = dy$ .

Note that if $D = d^2$ is a perfect square, then this problem can be solved using difference of squares. We would have $x^2 - Dy^2 = (x+dy)(x-dy) = 1$ , from which we can use casework to quickly determine the solutions.

Alternatively, if D is a nonsquare then there are infinitely many distinct solutions to the pell equation. To prove this it must first be shown that there is a single solution to the pell equation.

Claim: If D is a positive integer that is not a perfect square, then the equation $x^2-Dy^2 = 1$ has a solution in positive integers.

Proof: Let $c_{1}$ be an integer greater than 1. We will show that there exists integers $t_{1}$ and $w_{1}$ such that $t_{1}-w_{1}\sqrt{D} < \frac{1}{c_{1}}$ with $w_{1} \le c_{1}$ . Consider the sequence $l_{k} = [k\sqrt{D}+1] \rightarrow 0 \le l_{k}-k\sqrt{d} \le 1$ $\forall$ $0 \le k \le c_{1}$ . By the pigeon hole principle it can be seen that there exists i, j, and p such that i < j, $0\le i, j, p, \le c_{1}$ and

$\frac{p-1}{c_{1}} < l_{i}-i\sqrt{D} \le \frac{p}{c_{1}}, \frac{p-1}{c_{1}} < l_{j}-j\sqrt{D} \le \frac{p}{c_{1}}\rightarrow (l_{j}-l_{i})-(j-i)\sqrt{D} < \frac{1}{c_{1}} \rightarrow t_{1} = l_{j}-l_{i}, w_{1} = j-i$ .

So we now have

$t_{1}-w_{1}\sqrt{D} < \frac{1}{c_{1}} \rightarrow t_{1}+w_{1}\sqrt{D} < 2w_{1}\sqrt{D}+1\rightarrow t_{1}^2-Dw_{1}^2 < 2\frac{w_{1}}{c_{1}}\sqrt{D}+\frac{1}{c_{1}}<2\sqrt{D}+1$ .

We can now create a sequence of $t_{n}, w_{n}, c_{n}$ such that $t_{n}-w_{n}\sqrt{D} < \frac{1}{c_{n}}, t_{n}^2-Dw_{n}^2 < 2\sqrt{D}+1$ and $t_{n}-w_{n}\sqrt{D} > \frac{1}{c_{n+1}}$ which implies $t_{s} \not= t_{r}$ $\forall$ r and s. However we can see by the pigeon hole principle that there is another infinite sequence which will be denoted by $t_{y_{k}}, w_{y_{k}}$ such that $t_{y_{k}}^2-Dw_{y_{k}}^2 = h < 2\sqrt{D}+1$ . Once again, from the pigeon hole principle we can see that there exist integers f and g such that $t_{y_{f}}^2-Dw_{y_{f}}^2 = t_{y_{g}}^2-Dw_{y_{g}}^2 = H, t_{y_{f}} = t_{y_{g}}$ mod H, $w_{y_{f}} = w_{y_{g}}$ mod H, and $\frac{t_{y_{f}}}{w_{y_{f}}} \not= \frac{t_{y_{g}}}{w_{y_{g}}}$ . Define $X = t_{y_{f}}t_{y_{g}}-Dw_{y_{f}}w_{y_{g}}, Y = t_{y_{f}}w_{y_{g}}-t_{y_{g}}w_{y_{f}}$ and notice that $X^2-DY^2 = H^2$ . Also note that $X = t_{y_{f}}t_{y_{g}}-Dw_{y_{f}}w_{y_{g}} = t_{y_{f}}^2-Dw_{y_{f}}^2 = 0$ mod H which means that Y = 0 mod H also. We can now see that $\frac{X}{H}, \frac{Y}{H}$ is a nontrivial solution to pell's equation.

Family of solutions

Let $(x_{0}, y_{0})$ be the minimal solution to the equation $x^2-Dy^2 = 1$ . Note that if $(a,b), (c, d)$ are solutions to this equation then $(a^2-Db^2)(c^2-Dd^2) = (ac+Dbd)^2-D(cb+ad)^2 = 1$ which means $(ac+Dbd, cb+ad)$ is another solution. From this we can guess that $(x_{n}, y_{n})$ is obtained from $(x_{0}^2-Dy_{0}^2)^{n+1}$ . This does indeed generate all the solutions to this equation. Assume there was another solution $(p, q)$ . If $(p,q)$ is non-minimal, then there exists some integer $m$ such that

Next, multiply the inequality by $x_{m}-\sqrt{D}y_{m} to obtain:

1 < (p+\sqrt{D}q)(x_{m}-\sqrt{D}y_{m}) = (px_{m}-Dqy_{m})+\sqrt{D}(qx_{m}-py_{m})< x_{0}+y_{0}\sqrt{D}$ (Error compiling LaTeX. Unknown error_msg).

However, it can be seen that

$(px_{m}-Dqy_{m})^2-D(qx_{m}-py_{m})^2 = (p+\sqrt{D}q)(x_{m}-\sqrt{D}y_{m})(p-\sqrt{D}q)(x_{m}+\sqrt{D}y_{m}) = 1$

Meaning $(px_{m}-Dqy_{m}, qx_{m}-py_{m})$ is a solution smaller than the minimal solution which is a contradiction.

Therefore, such $(p,q)$ cannot exist and so the method of composition generates every possible solution to Pell's equation.

Q.E.D.

Continued fractions

The solutions to the Pell equation when $D$ is not a perfect square are connected to the continued fraction expansion of $\sqrt D$ . If $a$ is the period of the continued fraction and $C_k=P_k/Q_k$ is the $k$ th convergent, all solutions to the Pell equation are in the form $(P_{ia},Q_{ia})$ for positive integer $i$ .