Continued Fractions

⚡ Key Takeaways

A continued fraction expresses a number as an iterated sequence of nested fractions $a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cdots}}$ . 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.

💡 The Core Insight

Any real number $x$ splits uniquely into its integer part $a_0 = \lfloor x \rfloor$ 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.

DefinitionSimple Continued Fraction

A simple (regular) continued fraction is an expression

1

\quad x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}}

Derivation hint: This is the nested form; each $a_i$ is obtained by peeling off integer parts and inverting remainders. where $a_0 \in \mathbb{Z}$ and $a_1, a_2, \ldots \in \mathbb{Z}_{>0}$ are the partial quotients. We abbreviate this as $x = [a_0; a_1, a_2, a_3, \ldots]$ . The expansion is finite if it terminates: $x = [a_0; a_1, \ldots, a_n]$ .

DefinitionConvergents

The $n$ -th convergent $p_n/q_n$ is the value obtained by truncating after $a_n$ :

2

\quad \frac{p_n}{q_n} = [a_0; a_1, \ldots, a_n]

Derivation hint: Evaluate the finite continued fraction from the innermost level outward. The numerators and denominators satisfy the fundamental recurrence

3

\quad p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2}

Derivation hint: Replace $a_n$ in $[a_0;\ldots,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$ .

TheoremFundamental Properties of Convergents

For the convergents of any simple continued fraction:

(a) The determinant identity holds:

4

\quad p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}

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

(b) Consecutive convergents differ by

5

\quad \frac{p_n}{q_n} - \frac{p_{n-1}}{q_{n-1}} = \frac{(-1)^{n-1}}{q_n q_{n-1}}

Derivation hint: Divide [4] by $q_n q_{n-1}$ .

(c) Even convergents increase to $x$ , odd convergents decrease to $x$ , and

6

\quad \left| x - \frac{p_n}{q_n} \right| < \frac{1}{q_n q_{n+1}} \le \frac{1}{q_n^2}

Derivation hint: $x$ lies between consecutive convergents; the gap [5] bounds the error, and $q_{n+1} \ge q_n$ .

TheoremLagrange's Theorem on Periodicity

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

TheoremBest Approximation Property

If $p_n/q_n$ is a convergent of $x$ , then for every rational $p/q$ with $0 < q \le q_n$ and $p/q \ne p_n/q_n$ :

7

\quad |q_n x - p_n| < |q x - p|

Derivation hint: 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).

ProofThe 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 = \lfloor x_0 \rfloor$ . 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 = \lfloor x_1 \rfloor \ge 1$ . Continuing, $x_{n+1} = 1/(x_n - a_n)$ and $a_n = \lfloor x_n \rfloor$ .

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. $\blacksquare$

∎

ProofUniqueness of the Expansion

Suppose $[a_0; a_1, \ldots] = [b_0; b_1, \ldots]$ as real numbers. Taking floors of both sides (using that all later $a_i, b_i \ge 1$ force the tail to lie in $(0,1)$ ) gives $a_0 = b_0$ . Subtracting and inverting reduces to $[a_1; a_2, \ldots] = [b_1; b_2, \ldots]$ , and induction yields $a_i = b_i$ for all $i$ . The only ambiguity is the finite-case convention $[a_0;\ldots,a_n,1] = [a_0;\ldots,a_n+1]$ , removed by requiring the last partial quotient to exceed $1$ . $\blacksquare$

∎

mathematician · 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, \ldots]$ , 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.

🧠 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 $\pi = [3; 7, 15, 1, 292, \ldots]$ 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.

Figure

Geometric construction of convergents zig-zagging toward x

ExampleExpanding 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\cdot2+1)/(3\cdot1+0) = 7/3$
$p_2/q_2 = (4\cdot7+2)/(4\cdot3+1) = 30/13$
$p_3/q_3 = (2\cdot30+7)/(2\cdot13+3) = 67/29$ ✓

Verify [4]: $p_3 q_2 - p_2 q_3 = 67\cdot13 - 30\cdot29 = 871 - 870 = 1 = (-1)^{3-1}$ . ✓

\boxed{67/29 = [2;\,3,\,4,\,2]}

ExampleApproximating an irrational: √2

Given: Find the continued fraction of $\sqrt{2}$ and a rational approximation accurate to $10^{-3}$ .

Step 1: $\lfloor\sqrt2\rfloor = 1$ , so $a_0=1$ ; remainder $\sqrt2 - 1$ , reciprocal $1/(\sqrt2-1) = \sqrt2+1 \approx 2.414$ . Step 2: $\lfloor\sqrt2+1\rfloor = 2$ , so $a_1 = 2$ ; remainder $\sqrt2 - 1$ again — the process repeats. Therefore $\sqrt2 = [1; 2, 2, 2, \ldots] = [1; \overline{2}]$ , purely periodic (consistent with Lagrange's theorem, since $\sqrt2$ is a quadratic irrational).

Convergents via [3]:

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

Error bound from [6]: $|\sqrt2 - 99/70| < 1/(q_5 q_6)$ . Here $q_5=70$ , $q_6 = 2\cdot70+29 = 169$ , so error $< 1/(70\cdot169) \approx 8.5\times10^{-5} < 10^{-3}$ . ✓

\boxed{\sqrt{2} \approx 99/70 \approx 1.41428,\ \text{error} < 10^{-4}}

⚠️ Common mistake

Continued fraction convergents are NOT the same as decimal truncations. Truncating $\pi = 3.14159\ldots$ to $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 $\ge 1$ (for $i \ge 1$ ), but the convergents $p_n/q_n$ are not the partial quotients — students frequently conflate the two sequences.

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

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

connection

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 - Ny^2 = 1$ : the fundamental solution comes from the convergents of $\sqrt{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/(\sqrt5 q^2)$ , with $\sqrt5$ 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.

🔬 Where this appears

⏳ History

- c. 300 BCE — Euclid's algorithm (Elements VII) implicitly computes continued fractions of ratios, the algorithmic seed of the theory.

- 1572 — Rafael Bombelli approximates

\sqrt{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/\pi

.

- 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

\pi

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

\sqrt5

, pinning down the golden ratio's extremal role.

open-problem

The continued fraction of $\pi$ has no known pattern. Despite $e = [2;1,2,1,1,4,1,1,6,\ldots]$ following a clean rule, the expansion of $\pi = [3;7,15,1,292,\ldots]$ 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 $\pi$ (or any specific algebraic irrational of degree $\ge 3$ , like $\sqrt[3]{2}$ ) 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 $\pi$ or $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.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also