Difference between revisions of "Pell equation"

Revision as of 12:17, 23 June 2018

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}$.

However, it can be seen that$ (Error compiling LaTeX. Unknown error_msg)(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$ (Error compiling LaTeX. Unknown error_msg)(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$ .

Generalization

A Pell-like equation is a diophantine equation of the form $x^2 - Dy^2 = k$ , where $D$ is a natural number and $k$ is an integer.

Introductory Problems

Show that if $x$ and $y$ are the solutions to the equation $x^2 - 2y^2 = 1$ , then $6\mid xy$ .

@@ Line 22: / Line 22: @@
   <math>x_{m}+\sqrt{D}y_{m} < p+\sqrt{D}q < x_{m+1}+\sqrt{D}y_{m+1}</math>
-Next, multiply the inequality by <math> x_{m}-\sqrt{D}y_{m} to obtain:
+Next, multiply the inequality by <math> x_{m}-\sqrt{D}y_{m}</math> to obtain:
-< (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}</math>.
+< (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}<math>.
 However, it can be seen that
-<math>(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</math>
+</math>(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<math>
-Meaning <math>(px_{m}-Dqy_{m}, qx_{m}-py_{m})</math> is a solution smaller than the minimal solution which is a contradiction.
+Meaning </math>(px_{m}-Dqy_{m}, qx_{m}-py_{m})<math> is a solution smaller than the minimal solution which is a contradiction.
-Therefore, such <math>(p,q)</math> cannot exist and so the method of composition generates every possible solution to Pell's equation.
+Therefore, such </math>(p,q)$ cannot exist and so the method of composition generates every possible solution to Pell's equation.
 Q.E.D.

Page

Toolbox

Search