Solutions to x^2 - dy^2 = 1 and x^2 - dy^2 = -1

# Solutions to x^2 - dy^2 = 1 and x^2 - dy^2 = -1

Recall from the Pell's Equation page that Pell's equation is $x^2 - dy^2 = N$ where $d, N \in \mathbb{Z}$. We noted that Pell's equation has at most finitely many solutions if $d < 0$ or $d$ is a perfect square. We will now look at a special type of Pell's equation and when it has solutions, namely:

(1)
\begin{align} \quad x^2 - dy^2 = \pm 1 \end{align}

## Solutions to x^2 - dy^2 = 1

 Proposition 1: If $d > 0$ is not a perfect square and $(a, b)$ is a positive solution to $x^2 - dy^2 = 1$, i.e., $a, b > 0$ then $x^2 - dy^2 = 1$ has infinitely many solutions.
• Proof: Note that $x^2 - dy^2 = 1$ has the solution $(x, y) = (1, 0)$. Let $(a, b)$ be any solution to $x^2 - dy^2 = 1$. Then:
(2)
\begin{align} \quad a^2 - db^2 &= 1 \\ \quad (a + b\sqrt{d})(a - b\sqrt{d}) &= 1 \end{align}
• Squaring both sides of equation above yields:
(3)
\begin{align} \quad (a + b\sqrt{d})^2(a - b\sqrt{d})^2 &= 1 \\ \quad [a^2 + 2ab \sqrt{d} + b^2d][a^2 -2ab\sqrt{d} + b^2d] &= 1 \\ \quad [(a^2 + b^2d) + (2ab \sqrt{d})][(a^2 + b^2d) - (2ab \sqrt{d})] &= 1 \\ \quad (a^2 + b^2d)^2 - d(2ab)^2 &= 1 \end{align}
• So $(x, y) = (a^2 + b^2d, 2ab)$ is another solution to $x^2 - dy^2 = 1$. $\blacksquare$
 Proposition 2: If $d > 0$ is not a perfect square and $\frac{h_n}{k_n}$ is the $n^{\mathrm{th}}$ convergent of $\sqrt{d}$ then $h_n^2 - dk_n^2 = (-1)^{n-1} q_{n+1}$.

Recall that $\displaystyle{q_{n+1} = \frac{d - m_{n+1}^2}{q_n}}$ and $m_{n+1} = a_nq_n - m_n$.

 Corollary 3: Suppose that $d > 0$ and $d$ is not a perfect square. Let $r$ be the period of the continued fraction expansion of $\sqrt{d}$. Then $(\pm h_{rn - 1}, \pm k_{rn - 1})$ satisfies the equation $x^2 - dy^2 = (-1)^{rn}$.
 Corollary 4: If $d > 0$ is not perfect square then $x^2 - dy^2 = 1$ has a positive solution and hence infinitely many solutions.
• Proof: By corollary $3$, for every even $n$ we have that $nr$ is even, and so $(\pm h_{rn - 1}, \pm k_{rn - 1})$ is a solution to $x^2 - dy^2 = 1$ for every even $n$.
• Alternatively, we can generate a single positive solution by corollary 3 and then apply proposition 1. $\blacksquare$
 Theorem 5: Let $d > 0$ and $d$ not be a perfect square. If $(x_1, y_1)$ is the first positive solution to $x^2 - dy^2 = 1$ then all positive solutions to $x^2 - dy^2 = 1$ are of the form $x_n + y_n \sqrt{d} = (x_1 + y_1 \sqrt{d})^n$.

## Solutions to x^2 - dy^2 = -1

From corollary 3, if $r$ is even then $rn$ is always even and so $x^2 - dy^2 = -1$ cannot have solutions since $(-1)^{rn} = 1$. If $r$ is odd then $rn$ is odd infinitely often and so $x^2 - dy^2 = -1$ has infinitely many solutions by corollary 3. We summarize this below.

 Corollary 6: Suppose that $d > 0$ and $d$ is not a perfect square. Let $r$ be the period of the continued fraction expansion of $\sqrt{d}$. If $r$ is odd then the equation $x^2 - dy^2 = -1$ has infinitely many solutions, namely $\left (\pm h_{rn - 1}, \pm k_{rn - 1} \right )$ are solutions.

For example, consider the Pell's equation:

(4)
\begin{align} \quad x^2 - 13y^2 = -1 \end{align}

The continued fraction expansion of $\sqrt{d} = \sqrt{13}$ is:

(5)
\begin{align} \quad \sqrt{13} = \langle 3; \overline{1, 1, 1, 1, 6} \rangle \end{align}

So $r = 5$, which is odd. Corollary 2 says that $x^2 - 13y^2 = -1$ has solutions and furthermore, $(\pm h_{5r - 1}, k_{5n - 1} )$ are solutions for every $n$. If we see $n = 1$ then we see that $(h_4, k_4)$ is a particular solution. Let's verify this.

$n$ $a_n$ $h_n$ $k_n$
$-2$ - $0$ $1$
$-1$ - $1$ $0$
$0$ $3$ $3$ $1$
$1$ $1$ $4$ $1$
$2$ $1$ $7$ $2$
$3$ $1$ $11$ $3$
$4$ $1$ $18$ $5$

So $(h_4, k_4) = (18, 5)$. Note that indeed

(6)
\begin{align} \quad 18^2 - 13(5)^2 = -1 \end{align}