Solutions of Pell's Equation
If the continued fraction of
\[\sqrt{n}\]
has cycle length \[s\]
then \[p^2_{rs}-nq^2_{rs} =(-1)^{rs}, \; r=1, \; 2,...\]
.All solutions of
\[x^2-ny^2= \pm 1\]
are given in this way.\[\sqrt{14}= [ 3, \lt 1, \; 2, \; 1, \; 6 \gt ]\]
has cycle length \[s=4\]
and the convergents \[\frac{p_4}{q_4}, \; \frac{p_8}{q_8}, \; \frac{p_{12}}{q_{12}},...\]
satisfy \[p^2_k-14q^2_k=1\]
.\[\sqrt{29}= [ 5, \lt 2, \; 1, \; 1, \; 2, \; 10 \gt ]\]
has cycle length \[s=5\]
and the convergents \[\frac{p_5}{q_5}, \; \frac{p_{10}}{q_{10}}, \; \frac{p_{15}}{q_{15}},...\]
satisfy \[p^2_k-14q^2_k=-1\]
.Proof
For each
\[r \gt 1\]
we can write \[\sqrt{n}\]
as the continued fraction \[[ a_1, a_2, a_3,...,a_3, a_2, 2a_1,a_2,a_3,...,a_3,a_2,x ] \]
with \[rs+1\]
partial quotients, the last of which \[x\]
is not an integer. In fact\[\begin{equation} \begin{aligned} x &= [ \lt 2a_1, a_2, a_3,...,a_2, a_1 \gt ] \\ &= a_1+ [ \lt 2a_1, a_2, a_3,...,a_3,a_2, 2a_1 \gt ] \\ &= a_1+ \sqrt{n} \end{aligned} \end{equation}\]
The final three convergents of the above continued fraction for
\[\sqrt{n}\]
are \[\frac{p_{rs-1}}{q_{rs-1}}, \; \frac{p_{rs}}{q_{rs}}, \; \frac{xp_{rs}+p_{rs-1}}{xq_{rs}+q_{rs-1}}\]
.The last of these is equal to
\[\sqrt{n}\]
so \[\sqrt{n} (xq_{rs}+q_{rs-1} )=xp_{rs}+p_{rs-1}\]
. Use \[x=a_1+\sqrt{n}\]
to get \[\sqrt{n} ((a_1+\sqrt{n})q_{rs}+q_{rs-1} )=(a_1+\sqrt{n})p_{rs}+p_{rs-1}\]
.The last expression simplifies to
\[\sqrt{n}(a_1q_{rs}+q_{rs-1}-p_{rs})=a_1p_{rs}+p_{rs-1}-nq_{rs}\]
The right hand side of this equation is an integer while the left hand side is irrational, so both sides must equal zero. Hence
\[a_1q_{rs}+q_{rs-1}=p_{rs}\]
(1)\[a_1p_{rs}+p_{rs-1}=nq_{rs}\]
(2)\[p_{rs}\]
(1) minus \[q_{rs}\]
(2) gives\[p^2_{rs}-nq^2_{rs}=p_{rs}q_{rs-1}-p_{rs-1}q_{rs}=(-1)^{rs}\]
Using Properties of Convergents of Finite Continued Fractions for the last step/
