Continued Fractions of Rational Numbers

Run the Euclidean algorithm on $67$ and $24$, but keep the quotients instead of throwing them away. They spell out a new way to write $\frac{67}{24}$, as a tower of fractions, and its truncations are the best possible approximations by small fractions.

Notation. $$[q_0; q_1, q_2, \dots, q_k] = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{1}{\ddots + \cfrac{1}{q_k}}}}$$ The $q_i$ are the partial quotients; $q_0$ is the whole-number part and the rest are positive integers.

Why it works

If $a = bq_0 + r_1$, then $\frac{a}{b} = q_0 + \frac{r_1}{b} = q_0 + \cfrac{1}{b / r_1}$. Now do the same to $\frac{b}{r_1}$, which is the next line of the Euclidean algorithm, and so on. So the quotients of the algorithm are exactly the partial quotients, and the process stops because the algorithm stops: every rational number has a finite continued fraction.

Counting squares of each size in the Euclidean rectangle reads off the partial quotients of $\frac{67}{24}$, and the table lists the convergents.

Worked example: Rational to continued fraction

Write $\frac{67}{24}$ as a continued fraction.

$67 = 24 \cdot 2 + 19$, $\ 24 = 19 \cdot 1 + 5$, $\ 19 = 5 \cdot 3 + 4$, $\ 5 = 4 \cdot 1 + 1$, $\ 4 = 1 \cdot 4 + 0$.
The quotients, in order: $2, 1, 3, 1, 4$.

Answer: $\frac{67}{24} = [2; 1, 3, 1, 4]$.

Worked example: Continued fraction to rational

Write $[1; 2, 3, 4]$ as a fraction.

Start at the bottom: $3 + \frac{1}{4} = \frac{13}{4}$.
Next: $2 + \frac{4}{13} = \frac{30}{13}$.
Last: $1 + \frac{13}{30} = \frac{43}{30}$.

Answer: $\frac{43}{30}$.

Convergents. Cutting the continued fraction after $q_k$ gives the $k$-th convergent $\frac{p_k}{q_k}$. They can be computed from the top down: $$p_k = q_k p_{k-1} + p_{k-2}, \qquad q_k = q_k q_{k-1} + q_{k-2},$$ starting from $p_{-1} = 1$, $p_{-2} = 0$, $q_{-1} = 0$, $q_{-2} = 1$ (on the right, $q_k$ is the partial quotient). The convergents alternate below and above the true value and close in fast: $\left|\frac{a}{b} - \frac{p_k}{q_k}\right| < \frac{1}{q_k q_{k+1}}$.

Worked example: The convergents of 67/24

List the convergents of $[2; 1, 3, 1, 4]$.

$\frac{p_0}{q_0} = \frac{2}{1}$, $\ \frac{p_1}{q_1} = \frac{1 \cdot 2 + 1}{1 \cdot 1 + 0} = \frac{3}{1}$.
$\frac{p_2}{q_2} = \frac{3 \cdot 3 + 2}{3 \cdot 1 + 1} = \frac{11}{4}$, $\ \frac{p_3}{q_3} = \frac{11 + 3}{4 + 1} = \frac{14}{5}$, $\ \frac{p_4}{q_4} = \frac{4 \cdot 14 + 11}{4 \cdot 5 + 4} = \frac{67}{24}$.
They alternate: $2 < 2.75 < 2.791\overline{6} < 2.8 < 3$.

Answer: $\frac{2}{1}, \frac{3}{1}, \frac{11}{4}, \frac{14}{5}, \frac{67}{24}$.

Common mistake

Dropping the whole-number part $q_0$, or rebuilding the fraction from the outside in. $[1; 2, 3, 4]$ is not $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4}$; each partial quotient sits inside the one before it. Evaluate from the innermost term outward, as in the second example, or use the recurrence.

The same algorithm works for irrational numbers, where it never stops: $\pi = [3; 7, 15, 1, 292, \dots]$, with convergents $3$, $\frac{22}{7}$, $\frac{333}{106}$, $\frac{355}{113}$. The large 292 explains why $\frac{355}{113}$ is so astonishingly close to $\pi$. Square roots come next, in continued fractions of square roots.

Key idea

The quotients of the Euclidean algorithm on $a$ and $b$ are the partial quotients of $\frac{a}{b} = [q_0; q_1, \dots, q_k]$. Evaluate from the inside out; the convergents $\frac{p_k}{q_k}$ are ever better approximations.

Continued Fractions of Rational Numbers

Practice

Builds on

Leads to

Sources and further reading