Continued Fractions — Mathematics Knowledge System

Overview

A continued fraction expresses a number as an integer plus the reciprocal of another number, applied recursively: a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ⋯))). Every rational number has a finite continued fraction expansion, and computing it is literally the Euclidean algorithm run on the numerator and denominator — the quotients at each division step are exactly the continued-fraction terms. Irrational numbers get infinite expansions; famously, the expansion of an irrational is eventually periodic if and only if the number is a quadratic irrational (root of a degree-2 polynomial with integer coefficients), a theorem due to Lagrange. Truncating the expansion at each stage produces the 'convergents,' which are provably the best possible rational approximations to a given number for their denominator size — the reason continued fractions are used for calendar design (fractions of a year), gear ratios, and solving Pell's equation x² − Ny² = 1.

Intuition

Computing the continued fraction of a fraction a/b is the Euclidean algorithm wearing a different hat: at each step you take the integer part (the quotient) and recurse on the reciprocal of the remainder, exactly mirroring 'divide, take the remainder, repeat.' Truncating the expansion early is like rounding a decimal, but far smarter — because each new term corrects the previous approximation by the largest amount possible for the least increase in denominator, convergents are 'best approximations' in a precise, provable sense (nothing with a smaller or equal denominator gets closer).

Formal Definition

Definition

For a real number x, define a₀ = ⌊x⌋ and recursively xₖ₊₁ = 1/(xₖ − aₖ), aₖ₊₁ = ⌊xₖ₊₁⌋, giving the expansion:

x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}} =: [a_0; a_1, a_2, a_3, \ldots]

Continued fraction expansion

\frac{p_k}{q_k} = [a_0; a_1, \ldots, a_k], \qquad p_k = a_k p_{k-1} + p_{k-2}, \ \ q_k = a_k q_{k-1} + q_{k-2}

Convergent recurrence

\left| x - \frac{p_k}{q_k} \right| < \frac{1}{q_k q_{k+1}}

Convergents are best rational approximations

Worked Examples

Divide 47 by 17: quotient 2, remainder 13.
$47 = 2\cdot 17 + 13 \ \Rightarrow\ a_0 = 2$
Recurse on 17/13: quotient 1, remainder 4.
$17 = 1\cdot 13 + 4 \ \Rightarrow\ a_1 = 1$
Recurse on 13/4: quotient 3, remainder 1.
$13 = 3\cdot 4 + 1 \ \Rightarrow\ a_2 = 3$
Recurse on 4/1: quotient 4, remainder 0 — expansion terminates.
$4 = 4\cdot 1 + 0 \ \Rightarrow\ a_3 = 4$

Answer: 47/17 = [2; 1, 3, 4].

Practice Problems

Difficulty 2/10

Compute 17 mod 13.

Difficulty 6/10

Using [2; 1, 3, 4] for 47/17, compute the second convergent p₁/q₁ = [2; 1] and verify it approximates 47/17 ≈ 2.7647.

Difficulty 3/10

Find the continued fraction expansion of 7/3.

Quiz

Summary

A continued fraction [a₀; a₁, a₂, …] expresses a number via nested reciprocals; for rationals, computing it is exactly the Euclidean algorithm.
Truncations (convergents pₖ/qₖ) satisfy a linear recurrence and are the best possible rational approximations for their denominator size.
Lagrange's theorem: an irrational's expansion is eventually periodic exactly when the number is a quadratic irrational — key to solving Pell's equation.

References

WebsiteWikipedia — Continued fraction