Pell Equations and Continued Fractions

Suppose that we want to solve $p^2-2q^2=1$. This is similar to approximating $\sqrt{2}$ as $\frac{p}{q}$.

Right, we use continued fractions to approximate real numbers. Let's try to do that in this case. First, we find the continued fraction approximation for $\sqrt{2}$. $$\sqrt{2}=[1,2,2,2,\cdots]=[1,\overline{2}].$$ We find the convergents, which are really good approximations for $\sqrt{2}$. The first few are: $$\left\{\frac{1}{1},\frac{3}{2},\frac{7}{5},\frac{17}{12},\frac{41}{29},\cdots\right\}.$$ Let's see which ones work. $$\begin{align} \frac{1}{1}&:&1^2-2(1)^2&=-1\\ \frac{3}{2}&:&3^2-2(2)^2&=1\\ \frac{7}{5}&:&7^2-2(5)^2&=-1\\ \frac{17}{12}&:&17^2-2(12)^2&=1\\ \frac{41}{29}&:&41^2-2(29)^2&=-1 \end{align}$$

Therefore, some solutions are $(p,q)=(3,2),(17,2)$

Note that there is a pattern. It alternates between $-1$ and $1$. From this, we can conjecture that there are infinitely many integer solutions, namely every other convergent.

Similarly, we can solve any equation in the form $p^2-nq^2=1$ by finding the continued fraction expansion of $\sqrt{n}$ and considering the convergents. This doesn't work when $n$ is a square because then there's only one convergent!