Difference between revisions of "Pell equation"

Revision as of 13:54, 28 August 2020

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

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

Intermediate Problems

Find the largest integer $n$ satisfying the following conditions:

(i) $n^2$ can be expressed as the difference of two consecutive cubes;

(ii) $2n + 79$ is a perfect square. (Source)

@@ Line 1: / Line 1: @@
-A '''Pell equation''' is a type of [[diophantine equation]] in the form <math>x^2-Dy^2 = 1</math> for a [[natural number]] <math>D</math>. Generally, <math>D</math> is taken to be square-free, since otherwise we can "absorb" the largest square factor <math>d^2 | D</math> into <math>y</math> by setting <math>y' = dy</math>.
+A '''Pell equation''' is a type of [[diophantine equation]] in the form <math>x^2-Dy^2 = \pm1</math> for a [[natural number]] <math>D</math>. Generally, <math>D</math> is taken to be square-free, since otherwise we can "absorb" the largest square factor <math>d^2 | D</math> into <math>y</math> by setting <math>y' = dy</math>.
-Notice that if <math>D = d^2</math> is a perfect square, then this problem can be solved using [[difference of squares]]. We would have <math>x^2 - Dy^2 = (x+dy)(x-dy) = 1</math>, from which we can use casework to quickly determine the solutions.
+Note that if <math>D = d^2</math> is a perfect square, then this problem can be solved using [[difference of squares]]. We would have <math>x^2 - Dy^2 = (x+dy)(x-dy) = 1</math>, 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.
+Claim: If D is a positive integer that is not a perfect square, then the equation <math>x^2-Dy^2 = 1</math> 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})-(j-i)\sqrt{D} < \frac{1}{c_{1}} \rightarrow t_{1} = l_{j}-l_{i}, w_{1} = j-i</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 ==
-Given a smallest solution <math>z</math>, then all solutions are of the form <math>\pm z^n</math> for natural numbers <math>z</math>.
+Let <math>(x_{0}, y_{0})</math> be the minimal solution to the equation <math>x^2-Dy^2 = 1</math>. Note that if <math>(a,b), (c, d)</math> are solutions to this equation then <math>(a^2-Db^2)(c^2-Dd^2) = (ac+Dbd)^2-D(cb+ad)^2 = 1</math> which means <math>(ac+Dbd, cb+ad)</math> is another solution. From this we can guess that <math>(x_{n}, y_{n})</math> is obtained from <math>(x_{0}^2-Dy_{0}^2)^{n+1}</math>. This does indeed generate all the solutions to this equation. Assume there was another solution <math>(p, q)</math>. If <math>(p,q)</math> is non-minimal, then there exists some integer <math>m</math> such that
+ <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}</math> to obtain:
-{{stub}}
+<math>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}</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>
+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.
+Q.E.D.
 == Continued fractions ==
@@ Line 21: / Line 41: @@
 == Generalization ==
 A '''Pell-like equation''' is a diophantine equation of the form <math>x^2 - Dy^2 = k</math>, where <math>D</math> is a natural number and <math>k</math> is an integer.
+==Introductory Problems==
+Show that if <math>x</math> and <math>y</math> are the solutions to the equation <math>x^2 - 2y^2 = 1</math>, then <math>6\mid xy</math>.
+==Intermediate Problems==
+*Find the largest integer <math>n</math> satisfying the following conditions:
+:(i) <math>n^2</math> can be expressed as the difference of two consecutive cubes;
+:(ii) <math>2n + 79</math> is a perfect square. ([[2008 AIME II Problems/Problem 15|Source]])
 [[Category:Number theory]]

Page

Toolbox

Search