[proofplan] We run the complete quotient algorithm for the simple continued fraction of $\sqrt{D}$. Each complete quotient after the first is represented in the form $(\sqrt{D}+m_n)/d_n$ with integer parameters satisfying a divisibility condition and a pair of reducing inequalities. Those inequalities force the possible pairs $(m_n,d_n)$ to lie in a finite set, while the complete quotient map is reversible on that finite reduced set. Hence the sequence of pairs is periodic from its first reduced state, so the continued fraction is periodic after $a_0$; the last partial quotient of the minimal period is then computed from the return to the initial reduced state. [/proofplan] [step:Generate complete quotients and their integer recurrences] Define a sequence of [real numbers](/page/Real%20Numbers) $(\alpha_n)_{n \geq 0}$ and a sequence of integers $(a_n)_{n \geq 0}$ by \begin{align*} \alpha_0 &:= \sqrt{D}, \\ a_n &:= \lfloor \alpha_n \rfloor, \\ \alpha_{n+1} &:= \frac{1}{\alpha_n-a_n} \end{align*} for every $n \geq 0$. Since $D$ is not a square, $\sqrt{D}$ is irrational. By induction from the displayed recurrence, every $\alpha_n$ is irrational, so $\alpha_n-a_n \neq 0$ and the algorithm is defined for all $n \geq 0$. We define integer sequences $(m_n)_{n \geq 0}$ and $(d_n)_{n \geq 0}$ by \begin{align*} m_0 &:= 0, & d_0 &:= 1, \end{align*} and recursively, whenever \begin{align*} \alpha_n = \frac{\sqrt{D}+m_n}{d_n}, \end{align*} by \begin{align*} m_{n+1} &:= a_n d_n - m_n, \\ d_{n+1} &:= \frac{D-m_{n+1}^2}{d_n}. \end{align*} We prove by induction that $m_n,d_n \in \mathbb{Z}$, $d_n > 0$, $d_n \mid D-m_n^2$, and \begin{align*} \alpha_n = \frac{\sqrt{D}+m_n}{d_n} \end{align*} for all $n \geq 0$. The base case is $m_0=0$, $d_0=1$, and $\alpha_0=\sqrt{D}=(\sqrt{D}+0)/1$. Suppose the assertions hold at index $n$. Since $m_{n+1}=a_n d_n-m_n$, we have $m_{n+1} \in \mathbb{Z}$ and \begin{align*} m_{n+1} \equiv -m_n \pmod{d_n}. \end{align*} Therefore \begin{align*} D-m_{n+1}^2 \equiv D-m_n^2 \equiv 0 \pmod{d_n}, \end{align*} so $d_{n+1} \in \mathbb{Z}$. Also \begin{align*} \alpha_n-a_n &= \frac{\sqrt{D}+m_n-a_n d_n}{d_n} \\ &= \frac{\sqrt{D}-m_{n+1}}{d_n}. \end{align*} Since $\alpha_n-a_n>0$ and $d_n>0$, we get $m_{n+1}<\sqrt{D}$, hence $D-m_{n+1}^2>0$ and $d_{n+1}>0$. Finally, \begin{align*} \alpha_{n+1} &= \frac{1}{\alpha_n-a_n} \\ &= \frac{d_n}{\sqrt{D}-m_{n+1}} \\ &= \frac{d_n(\sqrt{D}+m_{n+1})}{D-m_{n+1}^2} \\ &= \frac{\sqrt{D}+m_{n+1}}{d_{n+1}}. \end{align*} This completes the induction. [/step] [step:Show every complete quotient after the first is reduced] For each $n \geq 0$, define the algebraic conjugate $\beta_n$ of $\alpha_n$ by \begin{align*} \beta_n := \frac{-\sqrt{D}+m_n}{d_n}. \end{align*} We prove that for every $n \geq 1$, \begin{align*} \alpha_n &> 1, & -1 &< \beta_n < 0. \end{align*} First, \begin{align*} m_1 = a_0, \qquad d_1 = D-a_0^2, \end{align*} so \begin{align*} \beta_1 = \frac{a_0-\sqrt{D}}{D-a_0^2} = -\frac{1}{\sqrt{D}+a_0}. \end{align*} Because $a_0 < \sqrt{D} < a_0+1$ and $a_0 \geq 1$ unless $D=2$ with the same inequality still valid, this gives $-1<\beta_1<0$. Also $\alpha_1=1/(\sqrt{D}-a_0)>1$ because $0<\sqrt{D}-a_0<1$. Now suppose $n \geq 1$ and $-1<\beta_n<0$. Since $\alpha_n>1$, we have $a_n=\lfloor \alpha_n \rfloor \geq 1$. The conjugate recurrence is obtained by applying algebraic conjugation to \begin{align*} \alpha_{n+1}=\frac{1}{\alpha_n-a_n}, \end{align*} namely \begin{align*} \beta_{n+1}=\frac{1}{\beta_n-a_n}. \end{align*} Because $\beta_n<0$ and $a_n \geq 1$, we have $\beta_n-a_n<-1$, and therefore \begin{align*} -1 < \frac{1}{\beta_n-a_n} < 0. \end{align*} Thus $-1<\beta_{n+1}<0$. Separately, $\alpha_{n+1}=1/(\alpha_n-a_n)>1$ because $0<\alpha_n-a_n<1$. By induction, the inequalities hold for all $n \geq 1$. [/step] [step:Place the complete quotient parameters in a finite reduced state set] For $n \geq 1$, the inequalities from the previous step give explicit bounds on $m_n$ and $d_n$. From $\beta_n<0$, \begin{align*} \frac{-\sqrt{D}+m_n}{d_n}<0. \end{align*} Since $d_n>0$, this gives $m_n<\sqrt{D}$. From $\beta_n>-1$, \begin{align*} \frac{-\sqrt{D}+m_n}{d_n}>-1, \end{align*} so \begin{align*} m_n>\sqrt{D}-d_n. \end{align*} From $\alpha_n>1$, \begin{align*} \frac{\sqrt{D}+m_n}{d_n}>1, \end{align*} so \begin{align*} d_n<\sqrt{D}+m_n<2\sqrt{D}. \end{align*} Combining $d_n<2\sqrt{D}$ with $m_n>\sqrt{D}-d_n$ gives \begin{align*} -\sqrt{D}<m_n<\sqrt{D}. \end{align*} Thus every pair $(m_n,d_n)$ with $n \geq 1$ belongs to the finite set \begin{align*} \mathcal{S} := \left\{ (m,d)\in \mathbb{Z}\times\mathbb{N} : -\sqrt{D}<m<\sqrt{D},\ 1\leq d<2\sqrt{D},\ d\mid D-m^2 \right\}. \end{align*} Since $\mathcal{S}$ is finite, the sequence $((m_n,d_n))_{n\geq 1}$ takes only finitely many values. [/step] [step:Use reversibility to force periodicity from the first reduced state] We show that the transition from $(m_n,d_n)$ to $(m_{n+1},d_{n+1})$ is injective on the reduced states that occur above. Suppose a reduced state $(m',d')$ is the image of a reduced state $(m,d)$. Then \begin{align*} d=\frac{D-(m')^2}{d'} \end{align*} is forced by the recurrence \begin{align*} d'=\frac{D-(m')^2}{d}. \end{align*} Once $d$ is known, the equation \begin{align*} m'=ad-m \end{align*} forces \begin{align*} m=ad-m' \end{align*} for the integer $a=\lfloor(\sqrt{D}+m)/d\rfloor$. The reduced inequalities for the predecessor require \begin{align*} \sqrt{D}-d < m < \sqrt{D}. \end{align*} Substituting $m=ad-m'$ gives \begin{align*} \frac{m'+\sqrt{D}-d}{d} < a < \frac{m'+\sqrt{D}}{d}. \end{align*} This is an open interval of length $1$. Its endpoints are irrational because $\sqrt{D}$ is irrational, so it contains at most one integer. Hence the predecessor state is unique, and the transition is injective on reduced states. Since the sequence $((m_n,d_n))_{n\geq 1}$ lies in the finite set $\mathcal{S}$, there exist indices $1\leq r<s$ such that \begin{align*} (m_r,d_r)=(m_s,d_s). \end{align*} If $r>1$, injectivity lets us step backwards repeatedly and obtain \begin{align*} (m_1,d_1)=(m_{s-r+1},d_{s-r+1}). \end{align*} Therefore the first reduced state $(m_1,d_1)$ repeats. Let $\ell\geq 1$ be the smallest integer such that \begin{align*} (m_{\ell+1},d_{\ell+1})=(m_1,d_1). \end{align*} The deterministic recurrence then gives \begin{align*} (m_{n+\ell},d_{n+\ell})=(m_n,d_n) \end{align*} for every $n\geq 1$. Since \begin{align*} a_n=\left\lfloor \frac{\sqrt{D}+m_n}{d_n}\right\rfloor \end{align*} for $n\geq 1$, it follows that \begin{align*} a_{n+\ell}=a_n \end{align*} for every $n\geq 1$. Thus the continued fraction of $\sqrt{D}$ is periodic after the initial term: \begin{align*} \sqrt{D}=[a_0;\overline{a_1,a_2,\dots,a_\ell}]. \end{align*} [/step] [step:Compute the final partial quotient of the minimal period] Because \begin{align*} (m_1,d_1)=(a_0,D-a_0^2) \end{align*} and $(m_{\ell+1},d_{\ell+1})=(m_1,d_1)$, the recurrence at index $\ell$ gives \begin{align*} m_{\ell+1} &= a_\ell d_\ell-m_\ell = a_0, \\ d_{\ell+1} &= \frac{D-m_{\ell+1}^2}{d_\ell}=D-a_0^2. \end{align*} Substituting $m_{\ell+1}=a_0$ into the second equality yields \begin{align*} \frac{D-a_0^2}{d_\ell}=D-a_0^2. \end{align*} Since $D$ is not a square, $D-a_0^2>0$, so $d_\ell=1$. The reduced inequality $-1<\beta_\ell<0$ now becomes \begin{align*} -1<-\sqrt{D}+m_\ell<0. \end{align*} Hence \begin{align*} \sqrt{D}-1<m_\ell<\sqrt{D}. \end{align*} Because $m_\ell$ is an integer and $a_0<\sqrt{D}<a_0+1$, this forces \begin{align*} m_\ell=a_0. \end{align*} Therefore \begin{align*} a_\ell = \left\lfloor \frac{\sqrt{D}+m_\ell}{d_\ell}\right\rfloor = \lfloor \sqrt{D}+a_0\rfloor = 2a_0. \end{align*} This proves the claimed periodic form and the final partial quotient formula for the minimal period. [/step]