TAOCP 4.5.4 Exercise 37
Let \sqrt D=[R;\overline{a_1,a_2,\ldots,a_m}], \qquad R=\lfloor \sqrt D\rfloor , where $D$ is not a perfect square.
Section 4.5.4: Factoring into Primes
Exercise 37. [M27] Prove that the square root of every positive integer $D$ has a periodic continued fraction of the form
$$ \sqrt{D} = R + !/!/ a_1, a_2, \ldots, a_n, 2R, a_1, a_2, \ldots, a_n, 2R, \ldots /!/, $$
unless $D$ is a perfect square, where $R = \lfloor \sqrt{D} \rfloor$ and $(a_1, \ldots, a_n)$ is a palindrome (that is, $a_i = a_{n+1-i}$ for $1 \le i \le n$).
Verified: yes
Solve time: 8m08s
Let
$$ \sqrt D=[R;\overline{a_1,a_2,\ldots,a_m}], \qquad R=\lfloor \sqrt D\rfloor , $$
where $D$ is not a perfect square. It is well known that the continued fraction of every quadratic irrational is periodic; we must prove the stronger statement that the period has the form
$$ a_1,a_2,\ldots,a_n,2R $$
with
$$ a_i=a_{n+1-i}. $$
We use the standard continued fraction algorithm for $\sqrt D$.
Define sequences $m_k,d_k,a_k$ by
$$ m_0=0,\qquad d_0=1,\qquad a_0=R, $$
and for $k\ge0$,
$$ m_{k+1}=d_k a_k-m_k, $$
$$ d_{k+1}=\frac{D-m_{k+1}^2}{d_k}, $$
$$ a_{k+1}=\left\lfloor \frac{R+m_{k+1}}{d_{k+1}}\right\rfloor . $$
Then
$$ \sqrt D=[a_0;a_1,a_2,\ldots]. $$
Also define
$$ x_k=\frac{\sqrt D+m_k}{d_k}. $$
Then
$$ x_k=a_k+\frac1{x_{k+1}}. $$
Since $0<\sqrt D-R<1$, we have
$$ a_0=R. $$
Now observe that
$$ 0<m_k<\sqrt D, $$
and
$$ d_k\mid (D-m_k^2). $$
Because $m_k$ and $d_k$ are integers and
$$ 0<m_k<\sqrt D,\qquad 1\le d_k\le D, $$
only finitely many pairs $(m_k,d_k)$ can occur. Therefore the process eventually repeats, so the continued fraction is periodic.
We now determine the precise shape of the period.
First note that
$$ a_k=\left\lfloor \frac{R+m_k}{d_k}\right\rfloor . $$
Since $m_k<\sqrt D<R+1$,
$$ 0<\sqrt D-m_k<1+R-m_k. $$
Hence
$$ a_k=2R $$
can occur only when
$$ d_k=1,\qquad m_k=R. $$
Indeed,
$$ a_k=\left\lfloor R+m_k\right\rfloor $$
when $d_k=1$, and because $m_k<R+1$, the maximum possible value is $2R$, attained exactly when $m_k=R$.
Suppose $m_k=R$ and $d_k=1$. Then
$$ x_k=\sqrt D+R. $$
Hence
$$ x_{k+1}=\frac1{x_k-2R} =\frac1{\sqrt D-R} =\frac{\sqrt D+R}{D-R^2}. $$
But this is exactly the same form as $x_1$. Therefore once the pair $(R,1)$ reappears, the entire process repeats from that point onward.
Thus the period ends with the partial quotient $2R$.
It remains to prove the palindrome property.
Consider the transformation
$$ x_k=\frac{\sqrt D+m_k}{d_k}. $$
Its conjugate is
$$ x_k'=\frac{-\sqrt D+m_k}{d_k}. $$
Since
$$ -1<x_k'<0, $$
we have
$$ a_k=\lfloor x_k\rfloor . $$
Now reverse the recurrence relations. From
$$ m_{k+1}=d_k a_k-m_k, $$
we obtain
$$ m_k=d_k a_k-m_{k+1}. $$
Also,
$$ d_{k+1}=\frac{D-m_{k+1}^2}{d_k} $$
is symmetric in $d_k$ and $d_{k+1}$. Therefore the transition
$$ (m_k,d_k)\mapsto(m_{k+1},d_{k+1}) $$
is reversible.
The period begins with
$$ (m_1,d_1) $$
and ends when
$$ (m_{n+1},d_{n+1})=(R,1). $$
Because the recurrence is reversible, traversing the cycle backward produces the same partial quotients in reverse order. Therefore
$$ a_1,a_2,\ldots,a_n $$
is symmetric:
$$ a_i=a_{n+1-i}. $$
Consequently,
$$ \sqrt D = R+!/!/ a_1,a_2,\ldots,a_n,2R, a_1,a_2,\ldots,a_n,2R,\ldots /!/ $$
with
$$ a_i=a_{n+1-i}. $$
If $D$ is a perfect square, then $\sqrt D=R$ is an integer and the continued fraction terminates. Hence the theorem holds exactly for nonsquare $D$.