Exercise 7.8.1* (Solutions to $x^2 -d y^2 = -1$)

Proof. Here $d$ is a positive integer which is not a perfect square.

By Theorem 7.25, all solutions of $x^2-d{y}^2=\pm 1$ are to be found among $x=h_n,y=k_n$, where $h_n∕k_n$ are the convergents of the expansion of $\sqrt{d}$. Since the sequences ${(h_n)}_{n\in \mathbb{N}}$ and ${(k_n)}_{n\in \mathbb{N}}$ are increasing, if $(x,y)$ and $(x^{\prime },y^{\prime })$ are positives solutions of $x^2-d{y}^2=\pm 1$, then $x\le x^{\prime }$ and $y\le y^{\prime }$, or $x\ge x^{\prime }$ and $y\ge y^{\prime }$. The relation defined on the set of positive solutions of $x^2-d{y}^2=\pm 1$ by

is a total order relation, and even a well-ordering. So we may consider a smallest positive solution of $x^2-d{y}^2=\pm 1$.

Let $(x_1,y_1)$ be the smallest positive solution of $x^2-y^{2}d=\pm 1$ (assuming that $x^2-d{y}^2=-1$ is solvable, we will prove later that $(x_1,y_1)$ is a solution of $x^2-y^{2}d=-1$). For every $n\in \mathbb{N}$, we define $(x_n,y_n)$, by $x_n+y_n\sqrt{d}={\left(x_1+y_1\sqrt{d}\right)}^n$.

Let $(s,t)$ be any positive solution of $x^2-y^{2}d=\pm 1$, so that

We know that $x_1\ge 1,y_1\ge 1$ and $d\ge 2$ thus $x_1+y_1\sqrt{d}>1$, so the sequence ${\left({(x_1+y_1\sqrt{d})}^n\right)}_{n\in \mathbb{N}}$ is strictly increasing, with limit $+\infty$. Since $s+t\sqrt{d}\ge 1$, there is some integer $m\ge 0$ such that

Assume for the sake of contradiction that ${(x_1+y_1\sqrt{d})}^m\ne s+t\sqrt{d}$, so that

Since $x_1^2-y_1^{2}d=\pm 1$, we have

we can multiply the inequality (1) by ${(x_1+y_1\sqrt{d})}^{-m}>0$ to obtain

Define integers $a$ and $b$ by $a+b\sqrt{d}={𝜀}^m(s+t\sqrt{d}){(x_1-y_1\sqrt{d})}^m$. Then

Moreover

therefore $|a-b\sqrt{d}|={(a+b\sqrt{d})}^{-1}$, where $1<a+b\sqrt{d}$, hence $|a-b\sqrt{d}|<1$, so

Using (4) and (5), we obtain

so $(a,b)$ is a positive solution of $x^2-y^{2}d=\pm 1$.

Since $(x_1,y_1)$ is the smallest positive solution of $x^2-y^{2}d=\pm 1$, then $x_1\le a$ and $y_1\le b$, so $x_1+y_1\sqrt{d}\le a+b\sqrt{d}$, in contradiction with (4).

This contradiction shows that $s+t\sqrt{d}={(x_1+y_1\sqrt{d})}^m$, so every solution of $x^2-y^{2}d=\pm 1$ is equal to $(x_n,y_n)$ for some index $n$.

If $(x_1,y_1)$ was a solution of $x^2-y^{2}d=+1$, then $x_n^2-y_n^{2}d=1$ for every $n\in \mathbb{N}$, therefore $x^2-y^{2}d=-1$ is not solvable, in contradiction with the hypothesis. This shows that

Moreover,

hence all solutions of $x^2-y^{2}d=-1$ are given by $(x_n,y_n)$, where $n=1,3,5,7,\dots$, and all solutions of $x^2-y^{2}d=1$ are given by $(x_n,y_n)$ with $n=2,4,6,8,\dots$.

In particular, the smallest solution of $x^2-d{y}^2=1$ is $(x_2,y_2)$, such that $x_2+y_2\sqrt{d}={(x_1+y_1\sqrt{d})}^2$. □