Continued Fractions

The equation

$$x^2-D{y}^2=1$$

over the integers for some nonsquare positive $D$ is known as the Pell equation. We consider a slighty more general variant of the equation:

$$x^2-D{y}^2=\pm 1$$

Theorem: If $D$ is a nonsquare positive integer whose continued fraction expansion has a repeating portion of $k$ terms, then $p_k,q_k$ is a solution of

$$x^2-D{y}^2=(-1{)}^k$$

Proof: Let $\sqrt{D}=[a_1;a_2,...]$ and $x_i=[a_i;a_{i+1},...]$. We have $x_2=x_{k+2}$ which means

$$\sqrt{D}=\frac{x_{k+2}{p}_{k+1}+p_k}{x_{k+2}{q}_{k+1}+q_k}=\frac{x_2{p}_{k+1}+p_k}{x_2{q}_{k+1}+q_k}$$

and $x_2=1/(\sqrt{D}-a_1)$, whence

$$\sqrt{D}=\frac{p_{k+1}+p_k(\sqrt{D}-a_1)}{q_{k+1}+q_k(\sqrt{D}-a_1)}$$

Rearranging, and equating rational and irrational parts yields

$$\begin{array}{rlr}{q}_{k+1}-a_1{q}_k-p_k& =& 0\\ p_{k+1}-a_1{p}_k-q_{k}D& =& 0\end{array}$$

Eliminating $a_1$:

$$-p_k{q}_{k+1}+q_k{p}_{k+1}+p_k^2-D{q}_k^2=0 \blacksquare$$

Theorem: If $p,q$ is a solution of $x^2-D{y}^2=\pm 1$ and $p,q$ are coprime then $p/q$ is a convergent of $\sqrt{D}$.

Proof: If $D>3$, then

$$\mid \frac{p}{q}-\sqrt{D}\mid =\frac{1}{(p+q\sqrt{D})q}<\frac{1}{2q^2}$$

and the result follows from a theorem on the accuracy of convergents. We can explicitly verify the cases $D=2,3$. $\blacksquare$

Theorem: If the $r$th convergent of $\sqrt{D}$ gives a solution of $x^2-D{y}^2=\pm 1$ then $k\mid r$ where $k$ is the number of terms in the period of the expansion.

Proof: Define $x_k=[a_k;a_{k+1},...]$. It is enough to show $x_{r+2}=x_2$ when the $r$th convergent gives a solution of the Pell equation: if $P,Q$ are the smallest positive integers such that $P^2-D{Q}^2=\pm 1$, then from the previous theorem, $P/Q$ is the $R$th convergent for some $R$, and we would have $x_{R+2}=x_2$, and also $k=R$ (otherwise we would have a smaller solution than $P,Q$ since $x_{k+2}=x_2$).

We replace $\pm 1$ with $(-1{)}^r$ in the equation since odd convergents are less than $\sqrt{D}$ while even convergents are greater.

We have

$$\sqrt{D}=\frac{p_r{x}_{r+1}+p_{r-1}}{q_r{x}_{r+1}+q_{r-1}}$$

which rearranges to

$$(p_r-\sqrt{D}{q}_r)x_{r+1}=-p_{r-1}+\sqrt{D}{q}_{r-1}$$

Applying $p_r^2-D{q}_r^2=(-1{)}^r$ gives

$$x_{r+1}=\sqrt{D}+(-1{)}^r(D{q}_r{q}_{r-1}-p_r{p}_{r-1})$$

That is, $x_{r+1}$ is $\sqrt{D}$ plus some integer. From our work on periodic continued fractions, we must have $x_2=x_{r+2} \blacksquare$

Theorem: The expansion of $\sqrt{D}$ for a nonsquare positive integer $D$ has the form

$$[a_1;a_2,a_3,a_4,...,a_4,a_3,a_2,2a_1,...]$$

with $a_2,a_3,...,2a_1$ repeating.

Proof: Considering the relationship between Euclid's algorithm and the computation of convergents, or directly from the recurrence relation, we have

$$\frac{q_{k+1}}{q_k}=[a_{k+1};a_k,...,a_2]$$

In the proof of our first theorem on Pell equations, we found

$$q_{k+1}-a_1{q}_k-p_k=0$$

if $p_k,q_k$ is a solution. Since $a_1+\frac{p_k}{q_k}=[2a_1;a_2,...,a_k]$, we have

$$[a_{k+1};a_k,...,a_2]=[2a_1;a_2,...,a_k] \blacksquare$$

If $x\prime ,y\prime$ and $x,y$ are solutions to $x^2-D{y}^2=\pm 1$, observe $x\prime >x$ if and only if $y\prime >y$. We use this in the following proof.

Theorem: If $p,q$ is the smallest positive solution of the equation $x^2-D{y}^2=\pm 1$, then all positive solutions $p_n,q_n$ are given by

$$(p+q\sqrt{D}{)}^n=p_n+\sqrt{D}{q}_n$$

where $n$ is odd for when the minus sign is chosen, and any integer when the plus sign is chosen.

Proof: Since $(p-q\sqrt{D}{)}^n=p_n-\sqrt{D}{q}_n$, we find $(p^2-D{q}^2{)}^n=p_n^2-D{q}^2$, thus $p_n,q_n$ indeed satisfies the equation if $p,q$ does.

First suppose the plus sign is chosen, and we have a standard Pell equation. Suppose $r,s$ is a solution such that

$$(p+q\sqrt{D}{)}^m<r+s\sqrt{D}<(p+q\sqrt{D}{)}^{m+1}$$

for some $m$. Divide through by $p_m+q_m\sqrt{D}$ to obtain

$$1<t+u\sqrt{D}<p+q\sqrt{D}$$

where $t+u\sqrt{D}=(r+s\sqrt{D})(p_m-q_m\sqrt{D})$.

Replacing $\sqrt{D}$ with $-\sqrt{D}$ and multiplying shows that $t,u$ is a (not necessarily positive) solution of the Pell equation. If $t,u>0$ then we have a smaller positive solution, contradicting the minimality of $p,q$.

We have $t>0$ because $r>s\sqrt{D}$ and $p_m>q_m\sqrt{D}$, as they are solutions of the Pell equation. We observe $u$ has the same sign as

$$(p_{m}s-q_{m}r)(p_{m}s+q_{m}r)=p_m^2{s}^2-q_m^2{r}^2=s^2(D{q}_m^2+1)-q_m^2(D{s}^2+1)=s^2-q_m^2$$

Since $s>q_m$ we are done.

For the minus sign variant of the equation, we argue similarly, with $m$ and $m+2$ where $m$ is odd. $\blacksquare$