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"
Line 7: Line 7:
 
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.
 
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 <math>c_{1}</math> be an integer greater than 1. We will show that there exists integers <math>t_{1}</math> and <math>w_{1}</math> such that <math>t_{1}-w_{1}\sqrt{D} < \frac{1}{c_{1}}</math> with <math>w_{1} \le c_{1}</math>. Consider the sequence <math>l_{k} = [k\sqrt{D}+1] \rightarrow 0 < l_{k}-k\sqrt{d} \le 1</math>  <math>\forall</math>  <math>0 \le k \le c_{1}</math>. By the pigeon hole principle it can be seen that there exists distinct integers i and j such that i < j and <math>\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}}</math> for some positive integer <math>1 \le p \le c_{1}</math>.
+
Proof: Let <math>c_{1}</math> be an integer greater than 1. We will show that there exists integers <math>t_{1}</math> and <math>w_{1}</math> such that <math>t_{1}-w_{1}\sqrt{D} < \frac{1}{c_{1}}</math> with <math>w_{1} \le c_{1}</math>. Consider the sequence <math>l_{k} = [k\sqrt{D}+1] \rightarrow 0 \le l_{k}-k\sqrt{d} \le 1</math>  <math>\forall</math>  <math>0 \le k \le c_{1}</math>. By the pigeon hole principle it can be seen that there exists i, j, and p such that i < j, <math>0\le i, j, p, \le c_{1}</math> and
  
 +
<math>\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})-(i-j)\sqrt{D} < \frac{1}{c_{1}} \rightarrow t_{1} = l_{j}-l_{i}, w_{1} = i-j</math>.
  
 +
So we now have
 +
 +
<math>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</math>.
 +
 +
We can now create a sequence of <math>t_{n}, w_{n}, c_{n}</math> such that <math>t_{n}-w_{n}\sqrt{D} < \frac{1}{c_{n}}, t_{n}^2-Dw_{n}^2 < 2\sqrt{D}+1</math> and <math>t_{n}-w_{n}\sqrt{D} > \frac{1}{c_{n+1}}</math> which implies <math>t_{s} \not= t_{r}</math> <math>\forall</math> r and s. However we can see by the pigeon hole principle that there is another infinite sequence which will be denoted by <math>t_{y_{k}}, w_{y_{k}}</math> such that <math>t_{y_{k}}^2-Dw_{y_{k}}^2 = h < 2\sqrt{D}+1</math>. Once again, from the pigeon hole principle we can see that there exist integers f and g such that <math>t_{y_{f}}^2-Dw_{y_{f}}^2 = t_{y_{g}}^2-Dw_{y_{g}}^2 = H, t_{y_{f}} = t_{y_{g}}</math> mod H, <math>w_{y_{f}} = w_{y_{g}}</math> mod H, and <math>\frac{t_{y_{f}}}{w_{y_{f}}} \not= \frac{t_{y_{g}}}{w_{y_{g}}}</math>. Define <math>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}}</math> and notice that <math>X^2-DY^2 = H^2</math>. Also note that <math>X = t_{y_{f}}t_{y_{g}}-Dw_{y_{f}}w_{y_{g}} = t_{y_{f}}^2-Dw_{y_{f}}^2 = 0</math> mod H which means that Y = 0 mod H also. We can now see that <math>\frac{X}{H}, \frac{Y}{H}</math> is a nontrivial solution to pell's equation.
  
 
== Family of solutions ==
 
== Family of solutions ==

Revision as of 20:55, 21 January 2011

A Pell equation is a type of diophantine equation in the form $x^2-Dy^2 = 1$ 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$.

Notice 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})-(i-j)\sqrt{D} < \frac{1}{c_{1}} \rightarrow t_{1} = l_{j}-l_{i}, w_{1} = i-j$.

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

Given a smallest solution $z$, then all solutions are of the form $\pm z^n$ for natural numbers $z$.

This article is a stub. Help us out by expanding it.

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.

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