Note - Proving Existence of Integral Solutions to General Pell's Equation

notepells-equation

General Pell’s Equation

$$x^2-d{y}^2=1\text{ for }d\in {\mathbb{Z}}^{+},d\ne \square .$$

Recall

Units in $\mathbb{Z}[\sqrt{d}]$ are $x+y\sqrt{d}$ where $x^2-d{y}^2=\pm 1$.

Theorem (Lagrange)

For all $$\begin{gathered} d\in {\mathbb{Z}}^{+},d \\ not=\square \end{gathered}$$, $x^2-d{y}^2=1$ has a solution in ${\mathbb{Z}}^{+}$.

Solving Specific Pell’s Equations

Example

Find all positive integral solutions to $x^2-7y^2=1$. $x^2=7y^2+1$ and compute right hand side at $y=1,2,\dots$ until it’s a square.

$7(1{)}^2+1=8\ne \square$ $7(2{)}^2+1=29\ne \square$ $7(3{)}^2+1=64=8^2$

So we have a solution: $x=8,y=3$.

Then, since $N(8+3\sqrt{7})=1$, $N((8+3\sqrt{7}{)}^n)=1$ and we can find infinitely many integral solutions of this form.

In fact, solutions of this form make up all integral solutions to this equation (up to sign on each value).

Lemma

For $d\in {\mathbb{Z}}^{+},d\ne \square$ there are infinitely many $x,y\in {\mathbb{Z}}^{+}$ such that $|x-y\sqrt{d}|<\frac{1}{y}$ ($|\frac{x}{y}-\sqrt{d}|<\frac{1}{y^2}$)

Example

$\sqrt{2}=1.414\cdots \approx \frac{14}{10}\approx \frac{141}{100}$ $|\frac{7}{5}-\sqrt{2}|=0.014\cdots <\frac{1}{5^2}=0.04$ $|\frac{141}{100}-\sqrt{2}|=0.004\cdots <\frac{1}{100^2}=\frac{1}{10^4}=0.0001$

Proof

Pick $m>1$ in $\mathbb{Z}$. Look at $m+1$ numbers $0,\sqrt{d},2\sqrt{d},\dots ,m\sqrt{d}$ and their decimal (fractional) parts in $[0,1)$.

$k\sqrt{d}=a_k+{\epsilon }_k$ with $a_k\in \mathbb{Z},a_k\ge 0$, and $0\le {\epsilon }_k\le 1$.

Break up $[0,1)$ into the $m$ intervals $[0,\frac{1}{m})$, $[\frac{1}{m},\frac{2}{m})$, $\dots$, $[\frac{m-1}{m},1)$.

The $m+1$ numbers ${\epsilon }_0,{\epsilon }_1,{\epsilon }_2,\dots ,{\epsilon }_m$ in $[0,1)$ lie in these $m$ intervals so the pigeonhole principle implies that some ${\epsilon }_k,{\epsilon }_{\ell }$ in the same $[\frac{j}{m},\frac{j+1}{m})$ for some $j=0,1,\dots ,m-1$. Without loss of generality, $k>\ell$.

$k\sqrt{d}-a_k={\epsilon }_k$ and $\ell \sqrt{d}-a_{\ell }={\epsilon }_{\ell }$ are in $[\frac{j}{m},\frac{j+1}{m})$, so $0\le |{\epsilon }_k-{\epsilon }_{\ell }|<\frac{1}{m}$.

$$\begin{array}{rl}0\le |k\sqrt{d}-a_k-(\ell \sqrt{d}-a_{\ell })|& <\frac{1}{m}\\ 0\le |(k-\ell )\sqrt{d}-(a_k-{\ell }_k)|& <\frac{1}{m}\\ 0\le |\underset{x}{(a_{\ell }-a_k)}+\underset{y\in {\mathbb{Z}}^{+}}{(k-\ell )}\sqrt{d}|& <\frac{1}{m}\\ |x-y\sqrt{d}|& <\frac{1}{m}\end{array}$$

$0\le \ell <k\le m⟹y=k-\ell <m⟹\frac{1}{m}<\frac{1}{y}$, so $|x-y\sqrt{d}|<\frac{1}{m}<\frac{1}{y}$.

$|x-y\sqrt{d}|<\frac{1}{y},y\in {\mathbb{Z}}^{+}$

$$\begin{array}{rl}⟹|x-y\sqrt{d}|<1⟹x& >y\sqrt{d}-1\\ & \ge \sqrt{d}-1\\ & \ge \sqrt{2}-1\\ & >0⟹x\in {\mathbb{Z}}^{+}.\end{array}$$

For each $m\in {\mathbb{Z}}^{+}$ we found an $x,y\in {\mathbb{Z}}^{+}$ such that $y<m$ and $|x-y\sqrt{d}|<\frac{1}{m}<\frac{1}{y}$.

Note $|x-y\sqrt{d}|>0$ since $\sqrt{d}\notin \mathbb{Q}$. Pick $m^{\prime }\in {\mathbb{Z}}^{+}$ such that $\frac{1}{m^{\prime }}<|x-y\sqrt{d}|$. Apply argument to get $|x^{\prime }-y^{\prime }\sqrt{d}|<\frac{1}{m^{\prime }},y^{\prime }<m^{\prime }<\frac{1}{y^{\prime }}$, etc, etc. $\square$

Remark

Try solving $x^2-61y^2=1$ by $x^2=61y^2+1$ and $y=1,2,3,\dots$ . Good luck…

Claim

We know by lemma that $|x-y\sqrt{d}|<\frac{1}{y}$ infinitely often in ${\mathbb{Z}}^{+}$.

Claim: $|x-y\sqrt{d}|<\frac{1}{y}⟹|x^2-d{y}^2|<2\sqrt{d}+1$. $x=x-y\sqrt{d}+y\sqrt{d}\le |x-y\sqrt{d}|+y\sqrt{d}<\frac{1}{y}+y\sqrt{d}\le 1+y\sqrt{d}$. Also see $x\le y\sqrt{d}+1$ by picture in proof of the lemma (still don’t have a good way to do diagrams…black box this I guess).

So

$$\begin{array}{rl}|x^2-d{y}^2|& =|(x+y\sqrt{d})(x-y\sqrt{d}))|\\ & =|x+y\sqrt{d}||x-y\sqrt{d}|\\ & =(x+y\sqrt{d})|x-y\sqrt{d}|\\ & =(x+y\sqrt{d})\frac{1}{y}\\ & \le (1+y\sqrt{d}+y\sqrt{d})\frac{1}{y}=(1+2y\sqrt{d})\frac{1}{y}\\ & =\frac{1}{y}+2\sqrt{d}\le 1+2\sqrt{d}.\end{array}$$

Infinitely many $(x,y)$ in ${\mathbb{Z}}^{+}$ such that $|x-y\sqrt{d}|<\frac{1}{y}$ $\to$ $x^2-d{y}^2=$ integer with absolute value $\le 2\sqrt{d}+1$, which means there are finitely many possibilities.

Pigeonhole principle $⟹$ there’s $M\in \mathbb{Z}$ with $|M|\le 2\sqrt{d}+1$ that is $x^2-d{y}^2$ with $|x-y\sqrt{d}|<\frac{1}{y}$ infinitely often.

For all these $x,y\in {\mathbb{Z}}^{+}$ where $x^2-d{y}^2=M$, consider pairs $(x\mathrm{mod}|M|,y\mathrm{mod}|M|)$, which gives $|M{|}^2$ such options.

Since we have infinitely many $x,y\in {\mathbb{Z}}^{+}$ with $x^2-d{y}^2=M$, by pigeonhole principle among these some $\mathrm{mod}|M|$ reduction $(x\mathrm{mod}|M|,y\mathrm{mod}|M|)$ occurs more than once: There are pairwise-distinct $x_1,y_1,x_2,y_2$ in ${\mathbb{Z}}^{+}$ such that $x_1^2-d{y}_1^2=M$, $x_2^2-d{y}_2^2=M$. $x_1\equiv x_2\mathrm{mod}|M|\to x_1=x_2+Ms$ for some $s\in \mathbb{Z}$. $y_1\equiv y_2\mathrm{mod}|M|\to y_1=y_2+Mt$ for some $t\in \mathbb{Z}$.

$x_1+y_1\sqrt{d}=(x_2+Ms)+(y_2+Mt)\sqrt{d}$ $x_1+y_1\sqrt{d}=x_2+y_2\sqrt{d}+M(s+t\sqrt{d})$ $x_1-y_1\sqrt{d}=x_2-y_2\sqrt{d}+M(s-t\sqrt{d})$ $M=x_2^2-d{y}_2^2=(x_2+y_2\sqrt{d})(x_2-y_2\sqrt{d})$

$\to x_1+y_1\sqrt{d}=x_2+y_2\sqrt{d}+9x_2+y_2\sqrt{d})(x_2-y_2\sqrt{d})(s+t\sqrt{d})$ $=(x_2+y_2\sqrt{d})(1+(x_2-y_2\sqrt{d})(s+t\sqrt{d}))=x+y\sqrt{d}$ for some $x,y\sqrt{d}$

$x_1+y_1\sqrt{d}=(xw+y_2\sqrt{d})(x+y\sqrt{d})$

Apply norms: $N(x_1+y_1\sqrt{d})=N(x_2+y_2\sqrt{d})N(x+y\sqrt{d})$ $x_1^2-d{y}_1^2=(x_2^2-d{y}_2^2)(x^2-d{y}^2)$ $M=M(x^2-d{y}^2)⟹x^2-d{y}^2=1$

Could $y$ be $0$? Then $x=\pm 1$, so $x_1+y_1\sqrt{d}=(x_2+y_2\sqrt{d})(\pm 1)=\pm (x_2+y_2\sqrt{d})$ $x_1,x_2,y_1,y_2$ in ${\mathbb{Z}}^{+}⟹x_1=\pm x_2,y_1=\pm y_2$ (same sign) $⟹x_1\ne -x_2,y_1\ne -y_2$. Thus $x_1=x_2$ and $y_1=y_2$, which violates how we picked $x_1,x_2,y_1,y_2$.