Solutions to x^2 - dy^2 = N

Solutions to x^2 - dy^2 = N

THeorem 1: Let $d > 0$ and $d$ not be a perfect square. Let $\frac{h_n}{k_n}$ be the $n^{\mathrm{th}}$ convergent of the continued fraction expansion of $\sqrt{d}$. If $|N| < \sqrt{d}$ and $(s, t)$ is a positive solution in lowest terms to $x^2 - dy^2 = N$ then $(s, t) = (h_n, k_n)$ for some $n \in \mathbb{N}$.
  • Proof: First suppose that $N > 0$. The other case is proved similarly. Suppose that $(s, t)$ is a positive solution in lowest terms to $x^2 - dy^2 = N$. Then $s^2 - dt^2 = N$. So:
(1)
\begin{align} \quad N = (s + t\sqrt{d})(s - t\sqrt{d}) \end{align}
  • Therefore:
(2)
\begin{align} \quad s - t \sqrt{d} &= \frac{N}{s + t \sqrt{d}} \\ \quad \frac{s}{t} - \sqrt{d} &= \frac{N}{t(s + t\sqrt{d})} \end{align}
  • Now since $N > 0$ and $N = (s + t\sqrt{d})(s - t\sqrt{d})$ with $s + t \sqrt{d} > 0$ we must have that $s - t\sqrt{d} > 0$. So $s > t\sqrt{d}$. Thus:
(3)
\begin{align} \quad \left | \frac{s}{t} - \sqrt{d} \right | &= \frac{N}{t(s + t\sqrt{d})} < \frac{N}{t(t\sqrt{d} + t\sqrt{d})} = \frac{N}{2t^2\sqrt{d}} \end{align}
  • But since $|N| < \sqrt{d}$ we have that $\frac{|N|}{\sqrt{d}} < 1$, and so:
(4)
\begin{align} \quad \left | \frac{s}{t} - \sqrt{d} \right | &< \frac{1}{2t^2} \end{align}
Theorem 2: Let $d > 0$ and $d$ not be a perfect square. Suppose that $|N| < \sqrt{d}$. If $(u, v)$ is the first positive solution to $x^2 - dy^2 = N$ and $(x_1, y_1)$ is the first positive solution to $x^2 - dy^2 = 1$ then all positive solutions to $x^2 - dy^2 = N$ are of the form $a + b\sqrt{d} = (u + v\sqrt{d})(x_1 + y_1\sqrt{d})^n$.

Recall that if $d > 0$ and $d$ not be a perfect square and 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$. This is the special case of Theorem 2 when $N = 1$. Thus, Theorem 2 can be thought of as a generalization of this theorem.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License