The continued fraction of $\sqrt{D}$ has symmetric period ending in $2a_0$

For every $n\ge 0$, [F1] and the floor inequality $a_n\le {\alpha }_n<a_n+1$ give $P_{n+1}=a_n{Q}_n-P_n<\sqrt{D}\mathrm{.}$ Also ${\alpha }_n>1$ for $n\ge 1$, so $Q_n<\sqrt{D}+P_n<2\sqrt{D}\mathrm{.}$ Since $P_n<\sqrt{D}$ for $n\ge 1$, the recurrence in [F1] gives $Q_n\le P_{n+1}+P_n<\sqrt{D}+P_{n+1},$ and therefore $Q_{n+1}=\frac{(\sqrt{D}-P_{n+1})(\sqrt{D}+P_{n+1})}{Q_n}>\sqrt{D}-P_{n+1}\mathrm{.}$ Hence $P_n<\sqrt{D}<P_n+Q_n(n\ge 1)\mathrm{.}$ So for $n\ge 1$ the pair $(P_n,Q_n)$ lies in the finite set of integer pairs with $-\sqrt{D}<P<\sqrt{D}$ and $0<Q<2\sqrt{D}$.

Let $S$ be the finite set of integer pairs $(P,Q)$ satisfying $Q>0,Q\mid D-P^2,P<\sqrt{D}<P+Q\mathrm{.}$ Step 1.1 shows that every $(P_n,Q_n)$ with $n\ge 1$ lies in $S$, and [F1] defines a successor map $T:S\to S$. This map is bijective: given $(P^{\mathrm{\prime }},Q^{\mathrm{\prime }})\in S$, put $Q:=\frac{D-(P^{\mathrm{\prime }}{)}^2}{Q^{\mathrm{\prime }}}\mathrm{.}$ The interval $(\sqrt{D}-Q,\sqrt{D})$ has irrational endpoints and length $Q$, so it contains exactly one integer $P$ in the residue class $-P^{\mathrm{\prime }}(\mathrm{m}\mathrm{o}\mathrm{d}Q)$. Then $a:=\frac{P+P^{\mathrm{\prime }}}{Q}\in \mathbb{Z},P^{\mathrm{\prime }}=aQ-P,Q^{\mathrm{\prime }}=\frac{D-(P^{\mathrm{\prime }}{)}^2}{Q},$ so $T(P,Q)=(P^{\mathrm{\prime }},Q^{\mathrm{\prime }})$. Since the orbit of $(P_1,Q_1)$ stays in the finite set $S$, there is a least $\mathrm{\ell }\ge 1$ with $T^{\mathrm{\ell }}(P_1,Q_1)=(P_1,Q_1)$, that is, $(P_{\mathrm{\ell }+1},Q_{\mathrm{\ell }+1})=(P_1,Q_1)$.

The recurrence at $n=0$ gives $P_1=a_0,Q_1=D-a_0^2\mathrm{.}$ Apply the inverse construction of step 2.1 to $(P_1,Q_1)$. Then $Q=\frac{D-a_0^2}{Q_1}=1,$ and the interval $(\sqrt{D}-1,\sqrt{D})$ contains the unique integer $a_0$. So the unique predecessor of $(P_1,Q_1)$ in $S$ is $(a_0,1)$. Since $(P_{\mathrm{\ell }},Q_{\mathrm{\ell }})$ is the predecessor of $(P_1,Q_1)$ along the cycle from step 2.1, one has $P_{\mathrm{\ell }}=a_0,Q_{\mathrm{\ell }}=1.$ The recurrence formula $P_{\mathrm{\ell }+1}=a_{\mathrm{\ell }}{Q}_{\mathrm{\ell }}-P_{\mathrm{\ell }}$ now gives $a_{\mathrm{\ell }}=P_{\mathrm{\ell }}+P_{\mathrm{\ell }+1}=a_0+a_0=2a_0\mathrm{.}$

We prove by induction on $j$ that $P_j=P_{\mathrm{\ell }-j+1}(1\le j\le \mathrm{\ell }),Q_{j-1}=Q_{\mathrm{\ell }-j+1}(1\le j\le \mathrm{\ell })\mathrm{.}$ The case $j=1$ is step 3.1 together with $Q_0=Q_{\mathrm{\ell }}=1$. Assume it for some $j<\mathrm{\ell }$. Then [F1] gives $Q_j=\frac{D-P_j^2}{Q_{j-1}}=\frac{D-P_{\mathrm{\ell }-j+1}^2}{Q_{\mathrm{\ell }-j+1}}=Q_{\mathrm{\ell }-j}\mathrm{.}$ Also $P_{j+1}$ and $P_{\mathrm{\ell }-j}$ are both integers congruent to $-P_j$ modulo $Q_j$, and both lie in the interval $(\sqrt{D}-Q_j,\sqrt{D})$ by step 1.1; by the uniqueness from step 2.1 they are equal. Thus $P_{j+1}=P_{\mathrm{\ell }-j},Q_j=Q_{\mathrm{\ell }-j},$ completing the induction. Therefore, for $1\le j<\mathrm{\ell }$, $a_j=\frac{P_j+P_{j+1}}{Q_j}=\frac{P_{\mathrm{\ell }-j+1}+P_{\mathrm{\ell }-j}}{Q_{\mathrm{\ell }-j}}=a_{\mathrm{\ell }-j}\mathrm{.}$

Steps 2.1, 3.1, and 4.1 show that the continued-fraction digits from $a_1$ onward repeat with period $\mathrm{\ell }$, that the last digit in one period is $2a_0$, and that the interior digits are palindromic. Hence $\sqrt{D}=[a_0;\overline{a_1,\dots ,a_{\mathrm{\ell }-1},2a_0}],a_j=a_{\mathrm{\ell }-j}(1\le j<\mathrm{\ell }),$ with first returned reduced state $(P_{\mathrm{\ell }},Q_{\mathrm{\ell }})=(a_0,1)$.