Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Pell equation"

(→‎Family of solutions)
(→‎Family of solutions)
Line 26: Line 26:
 
<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>(p+\sqrt{D}q, x_{m}-\sqrt{D}y_{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.
−
{{stub}}
+
 
 +
Therefore, such <math>(p,q)</math> cannot exist and so the method of composition generates every possible solution to Pell's equation.
 +
 
 +
Q.E.D.
  
 
== Continued fractions ==
 
== Continued fractions ==

Revision as of 12:14, 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 

$x_{m}+\sqrt{D}y_{m} < p+\sqrt{D}q < x_{m+1}+\sqrt{D}y_{m+1} \implies 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

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

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Pell_equation&oldid=95565"