Continued Fractions

A continued fraction expresses a number as an iterated sequence of nested fractions $a_{0} + \frac{1}{a _{1} + \frac{1}{a _{2} + \dots}}$ . Its key result: every real number has a continued fraction expansion that is finite iff the number is rational, and the truncations (convergents) are the best possible rational approximations. Applies to number theory, Diophantine approximation, Pell's equation, and the analysis of irrationality. Studied systematically by Euler, Lagrange, and Gauss in the 18th century, with roots in the Euclidean algorithm of antiquity.

A continued fraction represents a number $x$ in the form $a_{0} + 1/ (a_{1} + 1/ (a_{2} + \dots))$ , where the $a_{i}$ are integers called partial quotients. Unlike decimal expansions, which depend on an arbitrary base, continued fractions are intrinsic to the number and reveal its deepest arithmetic structure — periodicity in the expansion corresponds exactly to quadratic irrationals. They matter because they produce the best rational approximations to any real number (the convergents), solve Pell's equation, and give clean irrationality and transcendence criteria. The surprising fact: the simplest possible continued fraction, all $1$ 's, equals the golden ratio $φ$ , which is in a precise sense the "most irrational" number — the hardest to approximate by rationals.

The Core Insight

Any real number $x$ splits uniquely into its integer part $a_{0} = ⌊ x ⌋$ and a fractional remainder $x - a_{0} \in [0, 1)$ . The trick is to invert the remainder — replacing a small number in $[0, 1)$ by its reciprocal in $(1, \infty)$ — and repeat. This is precisely the Euclidean algorithm in disguise, and it terminates exactly when $x$ is rational. The list of integer parts you peel off at each stage is the continued fraction expansion.

Formal Statement

Simple Continued Fraction

A simple (regular) continued fraction is an expression

x = a_{0} + \frac{1}{a _{1} + \frac{1}{a _{2} + \frac{1}{a _{3} + \dots}}}

⟳This is the nested form; each

a_{i}

is obtained by peeling off integer parts and inverting remainders.

where $a_{0} \in Z$ and $a_{1}, a_{2}, \dots \in Z_{> 0}$ are the partial quotients. We abbreviate this as $x = [a_{0}; a_{1}, a_{2}, a_{3}, \dots]$ . The expansion is finite if it terminates: $x = [a_{0}; a_{1}, \dots, a_{n}]$ .

Convergents

The $n$ -th convergent $p_{n} / q_{n}$ is the value obtained by truncating after $a_{n}$ :

\frac{p _{n}}{q _{n}} = [a_{0}; a_{1}, \dots, a_{n}]

⟳Evaluate the finite continued fraction from the innermost level outward.

The numerators and denominators satisfy the fundamental recurrence

p_{n} = a_{n} p_{n - 1} + p_{n - 2}, q_{n} = a_{n} q_{n - 1} + q_{n - 2}

⟳Replace

a_{n}

[a_{0}; \dots, a_{n - 1}, a_{n}]

by the formal variable; induction on the structure of the nesting gives the linear recurrence.

with initial conditions $p_{- 1} = 1, p_{- 2} = 0, q_{- 1} = 0, q_{- 2} = 1$ .

Fundamental Properties of Convergents

For the convergents of any simple continued fraction:

(a) The determinant identity holds:

p_{n} q_{n - 1} - p_{n - 1} q_{n} = (- 1)^{n - 1}

⟳Induct using the recurrence [3]; the cross-terms telescope and the sign alternates.

(b) Consecutive convergents differ by

\frac{p _{n}}{q _{n}} - \frac{p _{n - 1}}{q _{n - 1}} = \frac{( - 1 ) ^{n - 1}}{q _{n} q _{n - 1}}

⟳Divide [4] by

q_{n} q_{n - 1}

(c) Even convergents increase to

x

, odd convergents decrease to

x

, and

x - \frac{p _{n}}{q _{n}} < \frac{1}{q _{n} q _{n + 1}} \leq \frac{1}{q _{n}^{2}}

⟳

x

lies between consecutive convergents; the gap [5] bounds the error, and

q_{n + 1} \geq q_{n}

Lagrange's Theorem on Periodicity

A simple continued fraction is eventually periodic if and only if $x$ is a quadratic irrational (a root of $a x^{2} + b x + c = 0$ with $a, b, c \in Z$ , $a \neq = 0$ , and non-square discriminant). It is purely periodic iff $x > 1$ and its conjugate $\overset{x}{ˉ}$ satisfies $- 1 < \overset{x}{ˉ} < 0$ (a reduced quadratic irrational).

Best Approximation Property

If $p_{n} / q_{n}$ is a convergent of $x$ , then for every rational $p / q$ with $0 < q \leq q_{n}$ and $p / q \neq = p_{n} / q_{n}$ :

∣ q_{n} x - p_{n} ∣ < ∣ q x - p ∣

⟳Solve

p = u p_{n} + v p_{n - 1}

q = u q_{n} + v q_{n - 1}

for integers

u, v

using [4]; sign analysis shows the convergent error is strictly smaller.

Convergents are thus the best rational approximations of the second kind — no rational with a smaller or equal denominator approximates $x$ more closely (after weighting by the denominator).

Why It Holds / Derivation

The Continued Fraction Algorithm and Termination

We construct the expansion of a real $x$ and prove the rational/irrational dichotomy.

Step 1 — Peel the integer part. Set

x_{0} = x

and

a_{0} = ⌊ x_{0} ⌋

. Then

x_{0} = a_{0} + (x_{0} - a_{0})

with the remainder

r_{0} = x_{0} - a_{0} \in [0, 1)

. Step 2 — Invert and repeat. If

r_{0} = 0

, stop. Otherwise define

x_{1} = 1/ r_{0} > 1

and

a_{1} = ⌊ x_{1} ⌋ \geq 1

. Continuing,

x_{n + 1} = 1/ (x_{n} - a_{n})

and

a_{n} = ⌊ x_{n} ⌋

. Step 3 — Rational case terminates. If

x = p / q

in lowest terms, the algorithm reproduces the Euclidean algorithm: writing

p = a_{0} q + r

, the partial quotients are exactly the quotients in successive divisions. Since remainders form a strictly decreasing sequence of nonnegative integers, the process halts after finitely many steps. Hence rationals have finite expansions. Step 4 — Irrational case is infinite. If

x

is irrational, no remainder

r_{n}

is ever zero (a zero remainder would express

x

as a finite continued fraction, which is rational by [2]–[3]). So the expansion is infinite. Step 5 — Convergence. From [5], the partial sums of

\sum (p_{n} / q_{n} - p_{n - 1} / q_{n - 1})

form an alternating series with terms

1/ (q_{n} q_{n - 1}) \to 0

(the

q_{n}

grow at least like Fibonacci numbers, so exponentially). Therefore

p_{n} / q_{n}

converges to a limit, and that limit is

x

by the nesting construction.

■

Uniqueness of the Expansion

Suppose $[a_{0}; a_{1}, \dots] = [b_{0}; b_{1}, \dots]$ as real numbers. Taking floors of both sides (using that all later $a_{i}, b_{i} \geq 1$ force the tail to lie in $(0, 1)$ ) gives $a_{0} = b_{0}$ . Subtracting and inverting reduces to $[a_{1}; a_{2}, \dots] = [b_{1}; b_{2}, \dots]$ , and induction yields $a_{i} = b_{i}$ for all $i$ . The only ambiguity is the finite-case convention $[a_{0}; \dots, a_{n}, 1] = [a_{0}; \dots, a_{n} + 1]$ , removed by requiring the last partial quotient to exceed $1$ . $■$

Leonhard Euler | 1707–1783

Euler was the first to develop continued fractions into a systematic theory. In his 1737 paper De fractionibus continuis dissertatio, he proved that $e$ has the elegant expansion $[2; 1, 2, 1, 1, 4, 1, 1, 6, \dots]$ , establishing $e$ 's irrationality. He discovered the recurrence relations for convergents, connected continued fractions to infinite series and products, and laid groundwork that Lagrange would complete with the periodicity theorem. Euler's notation and computational facility turned a curiosity into a pillar of analytic number theory.

Building Intuition

Think of a real number as a point on a number line. The integer part $a_{0}$ tells you which integer interval it sits in. The leftover fraction is small, so its reciprocal is large — and the size of that reciprocal tells you how close $x$ is to the integer $a_{0}$ : a huge $a_{1}$ means $x$ is barely above $a_{0}$ . Each partial quotient is a "zoom-in" step. Large partial quotients signal that a particular convergent is an exceptionally good approximation (the next one barely improves on it) — this is exactly why $π = [3; 7, 15, 1, 292, \dots]$ has the famous approximation $355/113$ : the $292$ means $355/113$ is astonishingly accurate. Conversely, all- $1$ 's (the golden ratio) means every approximation is as bad as continued fractions allow — no convergent is ever especially good.

Geometric construction of convergents zig-zagging toward x

Worked Examples

Expanding a rational number: 67/29

Given: Find the continued fraction of

67/29

via the Euclidean algorithm. Step 1:

67 = 2 \cdot 29 + 9

, so

a_{0} = 2

, remainder

9

. Step 2:

29 = 3 \cdot 9 + 2

, so

a_{1} = 3

, remainder

2

. Step 3:

9 = 4 \cdot 2 + 1

, so

a_{2} = 4

, remainder

1

. Step 4:

2 = 2 \cdot 1 + 0

, so

a_{3} = 2

, remainder

0

— stop.

Thus $67/29 = [2; 3, 4, 2]$ .

Check convergents using [3] with

p_{- 1} = 1, q_{- 1} = 0, p_{- 2} = 0, q_{- 2} = 1

$p_{0} / q_{0} = 2/1$
$p_{1} / q_{1} = (3 \cdot 2 + 1) / (3 \cdot 1 + 0) = 7/3$
$p_{2} / q_{2} = (4 \cdot 7 + 2) / (4 \cdot 3 + 1) = 30/13$
$p_{3} / q_{3} = (2 \cdot 30 + 7) / (2 \cdot 13 + 3) = 67/29$ ✓

Verify [4]: $p_{3} q_{2} - p_{2} q_{3} = 67 \cdot 13 - 30 \cdot 29 = 871 - 870 = 1 = (- 1)^{3 - 1}$ . ✓

67/29 = [2; 3, 4, 2]

Approximating an irrational: √2

Given: Find the continued fraction of

2

and a rational approximation accurate to

1 0^{- 3}

. Step 1:

⌊ 2 ⌋ = 1

, so

a_{0} = 1

; remainder

2 - 1

, reciprocal

1/ (2 - 1) = 2 + 1 \approx 2.414

. Step 2:

⌊ 2 + 1 ⌋ = 2

, so

a_{1} = 2

; remainder

2 - 1

again — the process repeats.

Therefore $2 = [1; 2, 2, 2, \dots] = [1; \overline{2}]$ , purely periodic (consistent with Lagrange's theorem, since $2$ is a quadratic irrational).

Convergents via [3]:

$1/1, 3/2, 7/5, 17/12, 41/29, 99/70$
$99/70 = 1.41428 \dots$ while $2 = 1.41421 \dots$

Error bound from [6]:

∣ 2 - 99/70∣ < 1/ (q_{5} q_{6})

. Here

q_{5} = 70

q_{6} = 2 \cdot 70 + 29 = 169

, so error

< 1/ (70 \cdot 169) \approx 8.5 \times 1 0^{- 5} < 1 0^{- 3}

. ✓

2 \approx 99/70 \approx 1.41428, error < 1 0^{- 4}

Common Misconceptions

Continued fraction convergents are NOT the same as decimal truncations. Truncating

π = 3.14159 \dots

314/100

gives a worse approximation than the convergent

355/113

, which uses a smaller denominator yet is accurate to six decimal places. Best-approximation (Theorem [7]) is a property of convergents, not of decimal rounding. Also beware: the partial quotients

a_{i}

are integers

\geq 1

(for

i \geq 1

), but the convergents

p_{n} / q_{n}

are not the partial quotients — students frequently conflate the two sequences.

Not every good approximation is a convergent — but every "very good" one is

The fraction $22/7$ is a convergent of $π$ ( $= [3; 7]$ ), and $355/113 = [3; 7, 15, 1]$ is too. But $311/99 \approx 3.1414$ approximates $π$ reasonably well, yet it is not a convergent. The precise statement (the converse direction) is: if $∣ x - p / q ∣ < 1/ (2 q^{2})$ , then $p / q$ must be a convergent. So merely "decent" approximations can be non-convergents, but anything beating the $1/ (2 q^{2})$ threshold is forced to be one. This shows the best-approximation property is sharp, not vacuous.

Connections

Continued fractions weave together several areas. The expansion algorithm is the Euclidean Algorithm applied to real numbers, so convergents inherit Bézout-type identities (the determinant relation [4] is exactly a Bézout coefficient). They give the complete solution to Pell's Equation $x^{2} - N y^{2} = 1$ : the fundamental solution comes from the convergents of $N$ at the end of its period. They are the principal tool in Diophantine Approximation, underlying Hurwitz's Theorem (every irrational has infinitely many $p / q$ with $∣ x - p / q ∣ < 1/ (5 q^{2})$ , with $5$ optimal precisely because of the golden ratio). Via the Gauss Map $x \mapsto {1/ x}$ they connect to Ergodic Theory and the Gauss–Kuzmin distribution, which describes the statistical frequency of partial quotients.

Real-World Applications

Calendar design. The tropical year is $\approx 365.2422$ days; its continued fraction $[365; 4, 7, 1, 3, \dots]$ yields the convergent giving the Gregorian rule (97 leap days per 400 years).
Gear ratios and orreries. Mechanical computers and planetary models use convergents to approximate irrational period ratios with small integer tooth counts — Huygens used $[7; 5, ...]$ -style convergents to design his planetarium gearing for Saturn.
Pell's equation and cryptography. Solving $x^{2} - N y^{2} = 1$ via $N$ 's expansion underlies certain factorization attacks and the structure of real quadratic fields.
Lattice reduction / signal processing. The Stern–Brocot tree and continued fractions identify rational resonances and aliasing frequencies; Wiener's attack on RSA recovers a small private exponent $d$ when $d / N$ has it as a convergent.
Music theory. The equal-tempered scale approximates $lo g_{2} (3/2) \approx 0.585$ ; its convergent $7/12$ gives the twelve-tone octave division.
Astronomy — synodic periods. Convergents of orbital period ratios predict planetary conjunction cycles and the Metonic cycle (19 years ≈ 235 lunar months).
Numerical analysis. Continued-fraction expansions of functions (e.g., $tan$ , $arctan$ , the error function) converge faster than power series in many regimes and are used in special-function libraries.

Historical Development

c. 300 BCE — Euclid's algorithm (Elements VII) implicitly computes continued fractions of ratios, the algorithmic seed of the theory.
1572 — Rafael Bombelli approximates $13$ using an iterative scheme equivalent to a continued fraction.
1613 — Pietro Cataldi develops continued fractions explicitly for square roots, introducing early notation.
1655 — John Wallis coins "continued fraction" (fractio continua) in his Arithmetica Infinitorum and gives an infinite product/fraction for $4/ π$ .
1737 — Euler's De fractionibus continuis establishes the systematic theory, proves $e$ 's expansion, and derives the convergent recurrences.
1768 — Lambert uses the continued fraction of $tan x$ to prove $π$ is irrational.
1770 — Lagrange proves the periodicity theorem: eventual periodicity ⟺ quadratic irrational, and applies continued fractions to solve Pell's equation completely.
1812 — Gauss studies the distribution of partial quotients (the Gauss–Kuzmin problem), founding the ergodic theory of continued fractions; Kuzmin resolves it rigorously in 1928.
1891 — Hurwitz proves the optimal approximation theorem with the constant $5$ , pinning down the golden ratio's extremal role.

Subtleties & Limits

The continued fraction of $π$ has no known pattern. Despite

e = [2; 1, 2, 1, 1, 4, 1, 1, 6, \dots]

following a clean rule, the expansion of

π = [3; 7, 15, 1, 292, \dots]

appears statistically random, and it is an open question whether its partial quotients are bounded or follow the Gauss–Kuzmin distribution. More broadly, it is unknown whether

π

(or any specific algebraic irrational of degree

\geq 3

, like

32

) has bounded partial quotients. Khinchin's theorem shows that for almost every real number the geometric mean of the partial quotients converges to Khinchin's constant

\approx 2.6854

— yet no explicit "natural" constant has been proven to obey this, and verifying it for

π

e

remains out of reach. The deep mystery is that cubic and higher algebraic irrationals have no known periodicity or pattern, in stark contrast to the perfectly periodic quadratic case.

Continued Fractions

The Core Insight

Formal Statement

Simple Continued Fraction

Convergents

Fundamental Properties of Convergents

Lagrange's Theorem on Periodicity

Best Approximation Property

Why It Holds / Derivation

The Continued Fraction Algorithm and Termination

Uniqueness of the Expansion

Leonhard Euler | 1707–1783

Building Intuition

Geometric construction of convergents zig-zagging toward x

Worked Examples

Expanding a rational number: 67/29

Approximating an irrational: √2

Common Misconceptions

Not every good approximation is a convergent — but every "very good" one is

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also

Before this

Where this leads