# Why are only $n-1$ convergents solution to Pell's Equations

Given any equation of form $x^2-ny^2 = 1$, where $n$ is positive, non-square integer, let $[a_0; \overline{a_1, a_2, \dots a_k}]$ denote the continued fraction $\sqrt{n}$.

Let $\frac{p_i}{q_i} = [a_0; a_1, a_2, \dots a_{(k-1)i}]$. Why is it true that the solution of the Pell's equation exists in $\left\{\frac{p_1}{q_1}, \frac{p_2}{q_2}, \dots\right\}$.

More specifically, why doesn't a solution exist outside the set?

By a solution, I mean $p_i^2 - nq_i^2=1$.

If $x,y$ are positive integers satisfying $x^2 - ny^2 = 1$, then $\frac{x}{y}$ is a good rational approximation to $\sqrt{n}$. A really good rational approximation:

\begin{align} && x^2 - ny^2 &= 1 \\ &\iff& \frac{x^2}{y^2} - n &= \frac{1}{y^2} \\ &\iff& \frac{x}{y} - \sqrt{n} &= \frac{1}{y^2\bigl(\sqrt{n} + \frac{x}{y}\bigr)} \end{align}

Since $\sqrt{n} + \frac{x}{y} > 2\sqrt{n} > 2$, it is such a good rational approximation to $\sqrt{n}$ that it must be one of the convergents. (Per a theorem of Legendre, if

$$\biggl\lvert \alpha - \frac{p}{q}\biggr\rvert < \frac{1}{2q^2}$$

then $\frac{p}{q}$ is a convergent of $\alpha$. Legendre's more precise theorem easily implies this corollary. Digging a little deeper, if $x^2 - ny^2 = m$ with $\lvert m\rvert < \sqrt{n}$ for positive integers $x,y$, then $\frac{x}{y}$ must be a convergent of $\sqrt{n}$. Note: If $m$ is not squarefree, then $\frac{x}{y}$ need not be in reduced form.)

And if we look at the (simple) continued fraction expansion of $\sqrt{n}$, we can write the $k^{\text{th}}$ complete quotient as

$$\xi_k = \frac{\sqrt{n} + b_k}{c_k}$$

with integers $0 \leqslant b_k < \sqrt{n}$ (and $b_k = 0$ only for $k = 0$) and $0 < c_k < 2\sqrt{n}$, where $b_{k+1}, c_{k+1}$ are given by

\begin{align} b_{k+1} &= a_kc_k - b_k, \\ c_{k+1} &= \frac{n - b_{k+1}^2}{c_k}, \end{align}

as is seen from

$$\xi_{k+1} = \frac{1}{\xi_k - a_k} = \frac{c_k}{\sqrt{n} + b_k - a_kc_k} = \frac{c_k}{\sqrt{n} - b_{k+1}} = \frac{c_k(\sqrt{n} + b_{k+1})}{n - b_{k+1}^2}\,.$$

One inductively verifies that $c_k$ divides $n - b_{k+1}^2 = n - b_k^2 + 2a_kb_kc_k - a_k^2c_k^2$ and that $b_k,c_k$ satisfy the given inequalities. Further one checks that the period of the continued fraction is complete at the first $k > 0$ with $c_k = 1$.

Now it is an interesting fact that if we write the $r^{\text{th}}$ convergent (in reduced form) as

$$\frac{x_r}{y_r} = [a_0, a_1, \dotsc, a_r]$$

then

$$x_r^2 - n y_r^2 = (-1)^{r+1}\cdot c_{r+1}\,.$$

So the continued fraction of $\sqrt{n}$ has period length $k$, then the positive integer solutions to $x^2 - ny^2 = 1$ are given precisely by the numerator and denominator of the convergents with index $ik - 1$, where $i$ is a positive integer which must be even in case $k$ is odd. If $i$ and $k$ are both odd, we get the solutions to $x^2 - ny^2 = -1$. [So in your question you have a small mistake, it must be $ik - 1$ instead of $(k-1)i$.]

Summary: There are no solutions outside that set because being a solution implies giving such a good rational approximation to $\sqrt{n}$ that it must be a convergent, and the convergents with other indices (than one less than a multiple of the period length) have $\lvert x_r^2 - n y_r^2\rvert > 1$.