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]$$


$$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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.