[proofplan] We prove the two implications separately. Termination implies rationality is immediate: a terminating continued fraction is a finite nested expression built from integer partial quotients using the field operations of $\mathbb{Q}$, hence lies in $\mathbb{Q}$. The reverse direction is the content of the argument. Starting from a rational $\theta = b_0/c_0$ in lowest terms, the continued fraction algorithm produces a sequence of rationals $\theta_i = b_i/c_i$, and we use the defining recursion to show that the denominator sequence $(c_i)$ is strictly decreasing in the positive integers. Well-ordering forces termination in at most $c_0$ steps. [/proofplan] [step:Set up the continued fraction algorithm and its invariants] Fix $\theta \in \mathbb{R}$. The continued fraction algorithm defines sequences $(a_i)_{i \geq 0}$ of integers (partial quotients) and $(\theta_i)_{i \geq 0}$ of real numbers (complete quotients) by \begin{align*} \theta_0 &:= \theta, \quad a_i := \lfloor \theta_i \rfloor, \quad \theta_{i+1} := \frac{1}{\theta_i - a_i} \text{ whenever } \theta_i \neq a_i. \end{align*} The algorithm terminates at step $i$ precisely when $\theta_i = a_i \in \mathbb{Z}$, in which case $\theta_{i+1}$ is not defined. For each $i \geq 0$ at which the algorithm has not yet terminated, $\theta_i - a_i \in [0, 1)$ and $\theta_i - a_i \neq 0$, so \begin{align*} \theta_{i+1} &= \frac{1}{\theta_i - a_i} > 1. \end{align*} In particular, $a_{i+1} = \lfloor \theta_{i+1} \rfloor \geq 1$ for all $i \geq 0$. [/step] [step:Prove termination implies rationality] Suppose the algorithm terminates at index $N$: then $\theta_N = a_N \in \mathbb{Z} \subset \mathbb{Q}$. The recursion $\theta_i = a_i + 1/\theta_{i+1}$ shows that if $\theta_{i+1} \in \mathbb{Q}^\times$, then $\theta_i = a_i + 1/\theta_{i+1} \in \mathbb{Q}$ (as $\mathbb{Q}$ is a field and $a_i \in \mathbb{Z} \subset \mathbb{Q}$). A reverse induction on $i$ from $N$ down to $0$ then shows $\theta_i \in \mathbb{Q}$ for each $i$: the base case is $\theta_N = a_N \in \mathbb{Q}$, and the inductive step uses $\theta_{i+1} \in \mathbb{Q}$ with $\theta_{i+1} > 1 > 0$ (hence nonzero) to conclude $\theta_i \in \mathbb{Q}$. In particular $\theta = \theta_0 \in \mathbb{Q}$. [/step] [step:Express each complete quotient as a reduced fraction] For the converse, suppose $\theta \in \mathbb{Q}$. Write $\theta_0 = b_0/c_0$ in lowest terms with $c_0 \geq 1$, so $\gcd(b_0, c_0) = 1$. We claim that whenever $\theta_i$ is defined, it can be written as $\theta_i = b_i/c_i$ in lowest terms with $c_i \geq 1$, and the pair $(b_i, c_i)$ is uniquely determined (up to simultaneous sign change, which we fix by requiring $c_i \geq 1$). This follows by induction: the base case $i = 0$ is the hypothesis. If $\theta_i = b_i/c_i$ in lowest terms with $c_i \geq 1$ and the algorithm has not terminated, then \begin{align*} \theta_{i+1} &= \frac{1}{\theta_i - a_i} = \frac{1}{\frac{b_i - a_i c_i}{c_i}} = \frac{c_i}{b_i - a_i c_i}. \end{align*} By the [Euclidean Algorithm divisibility invariant](/theorems/1697), $\gcd(b_i - a_i c_i, c_i) = \gcd(b_i, c_i) = 1$, so the fraction $c_i / (b_i - a_i c_i)$ is already in lowest terms. Fixing the sign convention $c_{i+1} \geq 1$, we set \begin{align*} b_{i+1} &= \operatorname{sgn}(b_i - a_i c_i) \cdot c_i, & c_{i+1} &= |b_i - a_i c_i|. \end{align*} [guided] The inductive claim is that every complete quotient $\theta_i$ produced by the algorithm on a rational input stays rational, and more precisely has a canonical reduced-fraction representation with a positive denominator. This matters because the proof of termination will compare denominators across steps, and we need those denominators to be unambiguous positive integers rather than up-to-sign objects. We carry out the induction. The base case $i = 0$ is the hypothesis $\theta_0 = b_0/c_0$ in lowest terms with $c_0 \geq 1$. Assume $\theta_i = b_i/c_i$ with $\gcd(b_i, c_i) = 1$ and $c_i \geq 1$. If the algorithm has terminated at step $i$, there is nothing to prove for $\theta_{i+1}$; otherwise $\theta_i \neq a_i$ and $\theta_{i+1}$ is defined. Writing out the definition, \begin{align*} \theta_{i+1} &= \frac{1}{\theta_i - a_i} = \frac{1}{(b_i - a_i c_i)/c_i} = \frac{c_i}{b_i - a_i c_i}. \end{align*} Is this fraction already in lowest terms? We compute $\gcd(c_i, b_i - a_i c_i)$. By the same manipulation that underpins Euclid's algorithm (see [Correctness of Euclid's Algorithm](/theorems/1697)), any common divisor of $c_i$ and $b_i - a_i c_i$ divides $b_i = (b_i - a_i c_i) + a_i c_i$, hence divides $\gcd(b_i, c_i) = 1$. So indeed $\gcd(c_i, b_i - a_i c_i) = 1$. To enforce $c_{i+1} \geq 1$, we multiply numerator and denominator by the sign of $b_i - a_i c_i$. Note $b_i - a_i c_i \neq 0$: if it vanished then $\theta_i = a_i$, contradicting non-termination at step $i$. So $\operatorname{sgn}(b_i - a_i c_i) \in \{+1, -1\}$ and we set \begin{align*} b_{i+1} &= \operatorname{sgn}(b_i - a_i c_i) \cdot c_i, & c_{i+1} &= |b_i - a_i c_i|, \end{align*} which gives $\theta_{i+1} = b_{i+1}/c_{i+1}$ in lowest terms with $c_{i+1} \geq 1$. [/guided] [/step] [step:Show the denominator sequence is strictly decreasing for $i \geq 1$] We show $c_{i+1} < c_i$ for all $i \geq 1$ at which $\theta_{i+1}$ is defined. For $i \geq 1$ we have $\theta_i > 1$ from Step 1, so $b_i/c_i > 1$ with $c_i \geq 1$, giving $b_i > c_i \geq 1$; in particular $b_i > 0$. Since $a_i = \lfloor \theta_i \rfloor \geq 1$, write $b_i = a_i c_i + (b_i - a_i c_i)$, which is the division of $b_i$ by $c_i$ with remainder $b_i - a_i c_i \in [0, c_i)$ (by definition of the floor function, $a_i c_i \leq b_i < (a_i + 1) c_i$). Non-termination at step $i$ excludes the value $0$, so \begin{align*} 0 &< b_i - a_i c_i < c_i. \end{align*} Therefore $b_i - a_i c_i > 0$ and $c_{i+1} = |b_i - a_i c_i| = b_i - a_i c_i < c_i$. [/step] [step:Conclude termination by well-ordering of positive integers] From Step 4, as long as the algorithm does not terminate, the sequence $(c_i)_{i \geq 1}$ is a strictly decreasing sequence of positive integers: \begin{align*} c_1 &> c_2 > c_3 > \cdots \geq 1. \end{align*} By the well-ordering principle for $\mathbb{N}$, no such infinite strictly decreasing sequence exists: any strictly decreasing sequence of positive integers must terminate after finitely many steps. Hence the algorithm terminates at some finite index $N$. Combined with Step 2, this gives both implications: the continued fraction expansion of $\theta$ terminates if and only if $\theta \in \mathbb{Q}$. [/step]