Difference between revisions of "Pell equation"

Revision as of 21:14, 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 < 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 distinct integers i and j such that i < j 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}}$ for some positive integer $1 \le p \le c_{1}$ .

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.

@@ Line 3: / Line 3: @@
 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.
-Alternatively, we would like to find the set of solutions to <math>z = x + y\sqrt{D} \in \mathbb{Z}[\sqrt{D}]</math> such that the [[norm]] of <math>z</math>, <math>\|z\| = z \cdot \overline{z} = (x + y \sqrt{D}) \cdot (x - y\sqrt{D}) = 1</math>.
+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 <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>.
 == Family of solutions ==

Page

Toolbox

Search

Difference between revisions of "Pell equation"

Revision as of 21:14, 21 January 2011

Family of solutions

Continued fractions

Generalization