Convergents of Simple Continued Fraction are Rationals in Canonical Form

From ProofWiki
Jump to: navigation, search

Theorem

Let $n \in \N \cup \{\infty\}$ be an extended natural number.

Let $\left[{a_0, a_1, a_2, \ldots}\right]$ be a simple continued fraction in $\R$ of length $n$.

Let $p_0, p_1, p_2, \ldots$ and $q_0, q_1, q_2, \ldots$ be its numerators and denominators.

Let $C_0, C_1, C_2, \ldots$ be the convergents of $\left[{a_0, a_1, a_2, \ldots}\right]$.


For all $k \ge 1$, $\dfrac {p_k} {q_k}$ is in canonical form:

$p_k$ and $q_k$ are coprime
$q_k > 0$.


Proof

Let $k \geq 1$.

Let $d = \gcd \left\{{p_k, q_k}\right\}$.

From Common Divisor Divides Integer Combination:

$p_k q_{k-1} - p_{k-1} q_k$ is a multiple of $d$.


From Difference between Adjacent Convergents of Simple Continued Fraction:

$d \mathrel \backslash \left({-1}\right)^{k+1}$

where $\backslash$ denotes divisibility.

It follows that:

$d = 1$


By:

$q_0 = 1$
Denominators of Simple Continued Fraction are Strictly Increasing

It follows that $q_k > 0$ for all $k \ge 0$.

$\blacksquare$