Exercise 7.8.12 ( If $p\equiv 1 \pmod 4$, then $x^2 - p y^2 = -1$ is solvable)

Proof. Suppose that $x^2-p{y}^2=1$, where $p\equiv 1(\mathit{mod}4)$. Then $x^2-y^2\equiv 1(\mathit{mod}4)$, so $x$ and $y$ have distinct parity.

If $x$ is even and $y$ is odd, then $x^2\equiv 0(\mathit{mod}4)$ and $y^2\equiv 1(\mathit{mod}4)$, so $x^2-y^2\equiv -1(\mathit{mod}4)$, which is false. Therefore $x$ is odd and $y$ is even.

By Theorem 7.25, since $p$ is not a perfect square, $x^2-p{y}^2=1$ has positive solutions. We define $(x_0,y_0)$ as a positive solution with $y_0$ minimal.

Let $d=g.c.d(x_0+1,x_0-1)$. Then $d\ge 0$, $d\mid x_0-1$ and $d\mid x_0+1$, thus $d\mid (x_0+1)-(x_0-1)=2$. Therefore $d=1$ or $d=2$. moreover $x_0$ is odd, thus $2\mid x_0-1$ and $2\mid x_0+1$, so $2\mid d$. Hence $d=2$:

Since $x_0^2-1=p{y}_0^2$, $p\mid (x_0-1)(x_0+1)$, thus $p\mid x_0-1$ or $p\mid x_0+1$.

• Case 1. If $p\mid x_0-1$, then

  $$\begin{array}{lll}\hfill \left(\frac{x_0-1}{2p}\right)\left(\frac{x_0+1}{2}\right)={\left(\frac{y_0}{2}\right)}^2.& & \hfill \text{(2)}\end{array}$$

  where $\frac{x_0-1}{2p}$, $\frac{x_0+1}{2}$, $\frac{y_0}{2}$ are integers. Moreover, by (1), $\frac{x_0-1}{2}\wedge \frac{x_0+1}{2}=1$, a fortiori

  $$\begin{array}{lll}\hfill \frac{x_0-1}{2p}\wedge \frac{x_0+1}{2}=1.& & \hfill \text{(3)}\end{array}$$

  By (2) and (3), Lemma 5.4 p. 232 shows that there are integers $u\ge 0$, $v\ge 0$ such that

  $$\frac{x_0-1}{2p}=u^2,\frac{x_0+1}{2}=v^2,$$

  so

  $$\begin{array}{lll}\hfill x_0-1=2p{u}^2,x_0+1=2v^2,y_0=2\mathit{uv}.& & \hfill \text{(4)}\end{array}$$

• Case 2. If $p\mid x_0-1$, then

  $$\begin{array}{lll}\hfill \left(\frac{x_0-1}{p}\right)\left(\frac{x_0+1}{2p}\right)={\left(\frac{y_0}{2}\right)}^2.& & \hfill \text{(5)}\end{array}$$

  We obtain similarly

  $$\begin{array}{lll}\hfill x_0-1=2u^2,x_0+1=2p{v}^2.& & \hfill \text{(6)}\end{array}$$

Consider the case 1. By (4), $v^2-p{u}^2=1$. Moreover $y_0=2\mathit{uv}>0$, thus $0<u<y_0$, in contradiction with the minimality of $y_0$. Therefore case 1 never occurs, and case 2 is true. By (6),

This shows that $x^2-p{y}^2=-1$ is solvable.

In conclusion, if $p\equiv 1(\mathit{mod}4)$, then the equation $x^2-p{y}^2=-1$ has an integral solution. □