Continued Fractions and Diophantine Approximation

⚡ Key Takeaways

Continued fractions express real numbers as nested fractions $a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cdots}}$ , and their truncations (convergents) are the provably best rational approximations to a real number. Key result: the convergents $p_n/q_n$ satisfy $|x - p_n/q_n| < 1/q_n q_{n+1} \le 1/q_n^2$ , and any fraction approximating $x$ better than $1/2q^2$ must be a convergent. Applies to: Diophantine approximation, transcendence theory, dynamical systems, cryptography (Wiener attack), and Pell's equation. Who/when: Euler, Lagrange (18th c.), Gauss, Hurwitz, Khinchin, Roth (20th c.).

💡 The Core Insight

A real number is "complicated" to approximate exactly when its continued fraction has large partial quotients, and "simple" (badly approximable) when they stay bounded. The Euclidean algorithm run on the pair $(x, 1)$ generates the partial quotients; its remainders generate the convergents. Truncating the expansion gives rationals that hug $x$ more tightly than any rational of comparable or smaller denominator — the convergents are the unique best approximations of the second kind. All of classical Diophantine approximation (Dirichlet, Hurwitz, Liouville, Roth) is a quantitative study of the growth of the denominators $q_n$ relative to the size of the error.

DefinitionSimple Continued Fraction and the Algorithm

For $x \in \mathbb{R}$ , define the continued fraction algorithm by $x_0 = x$ and, while $x_n \notin \mathbb{Z}$ ,

1

\quad a_n = \lfloor x_n \rfloor, \qquad x_{n+1} = \frac{1}{x_n - a_n}.

Derivation hint: split each $x_n$ into its integer part $a_n$ and fractional part $\{x_n\} \in [0,1)$ , then invert the fractional part to expose the next integer. The resulting sequence yields

2

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

Derivation hint: unwind [1] recursively: $x = a_0 + 1/x_1$ , $x_1 = a_1 + 1/x_2$ , etc. The expansion terminates iff $x \in \mathbb{Q}$ . For irrational $x$ it is infinite and unique.

DefinitionConvergents and Recurrences

The $n$ -th convergent is the rational $p_n/q_n = [a_0; a_1, \dots, a_n]$ , computed by 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},

with initial conditions $p_{-1}=1,\ p_{-2}=0,\ q_{-1}=0,\ q_{-2}=1$ . Derivation hint: matrix form — the product $\prod_{k=0}^n \begin{pmatrix} a_k & 1 \\ 1 & 0 \end{pmatrix}$ has columns $(p_n, q_n)$ and $(p_{n-1}, q_{n-1})$ ; induction on the last factor gives [3]. The convergents satisfy the determinant identity

4

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

Derivation hint: the matrix above has determinant $\prod (-1) = (-1)^{n+1}$ ; equate this to $p_n q_{n-1} - p_{n-1}q_n$ . and consequently

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}$ .

TheoremApproximation Quality of Convergents

For irrational $x = [a_0; a_1, a_2, \dots]$ with convergents $p_n/q_n$ ,

6

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

Derivation hint: write $x = [a_0;\dots,a_n,x_{n+1}]$ where $x_{n+1} > a_{n+1}\ge 1$ ; then $x = \frac{x_{n+1}p_n + p_{n-1}}{x_{n+1}q_n + q_{n-1}}$ , subtract $p_n/q_n$ , use [4], and bound $x_{n+1}$ . Moreover the convergents straddle $x$ : even-indexed ones increase to $x$ from below, odd-indexed ones decrease to $x$ from above.

TheoremBest Approximation Property

If $p/q$ (in lowest terms, $q \ge 1$ ) satisfies $|qx - p| < |q_n x - p_n|$ for some $n$ , then $q > q_n$ . Equivalently, the convergents are exactly the best rational approximations of the second kind: no fraction with denominator $\le q_n$ approximates $x$ better in the sense of minimizing $|qx - p|$ . In particular, if

7

\quad \left| x - \frac{p}{q} \right| < \frac{1}{2q^2},

then $p/q$ is a convergent of $x$ . Derivation hint: suppose $p/q$ satisfies [7] but is not a convergent; locate $n$ with $q_n \le q < q_{n+1}$ , express $(p,q)$ in the basis $\{(p_n,q_n),(p_{n-1},q_{n-1})\}$ via [4], and derive a contradiction on sizes.

TheoremHurwitz's Theorem — Optimal Constant

For every irrational $x$ , infinitely many rationals $p/q$ satisfy

8

\quad \left| x - \frac{p}{q} \right| < \frac{1}{\sqrt{5}\, q^2}.

The constant $\sqrt 5$ is best possible: for the golden ratio $\varphi = \tfrac{1+\sqrt 5}{2} = [1;1,1,\dots]$ , any larger constant $C > \sqrt 5$ admits only finitely many solutions to $|x - p/q| < 1/(Cq^2)$ . Derivation hint: among any three consecutive convergents at least one beats $1/\sqrt5 q^2$ , shown by the identity relating $q_{n-1}/q_n$ ratios; for optimality use that $x_{n+1} \to \varphi$ for the golden ratio so the constant saturates at $\sqrt5$ .

ProofBest Approximation Property — Equation 7

Step 1. Suppose $p/q$ is in lowest terms with $|x - p/q| < 1/(2q^2)$ , and assume for contradiction $p/q$ is not a convergent. Choose $n$ so that $q_n \le q < q_{n+1}$ (possible since the $q_n$ strictly increase for $n \ge 1$ ).

Step 2. By the best-approximation theorem, $|q_n x - p_n| \le |q x - p|$ . Multiply the hypothesis by $q$ : $|qx - p| < 1/(2q)$ .

Step 3. Consider the integer $N = p q_n - p_n q$ . Since $p/q \ne p_n/q_n$ (else $p/q$ is a convergent), $N \ne 0$ , so $|N| \ge 1$ . Write

9

\quad \frac{N}{q q_n} = \frac{p}{q} - \frac{p_n}{q_n} = \left(\frac{p}{q} - x\right) + \left(x - \frac{p_n}{q_n}\right).

Derivation hint: add and subtract $x$ ; the left equality is just clearing denominators.

Step 4. Bound the right side using the triangle inequality, the hypothesis, and [6]:

10

\quad \frac{1}{q q_n} \le \left|\frac{N}{q q_n}\right| < \frac{1}{2q^2} + \frac{1}{q_n q_{n+1}} \le \frac{1}{2q^2} + \frac{1}{q q_n}\cdot\frac{q}{q_{n+1}}.

Derivation hint: $|x - p_n/q_n| < 1/(q_n q_{n+1})$ by [6], and $q_n \le q$ .

Step 5. Since $q < q_{n+1}$ , we get $q/q_{n+1} < 1$ , and careful comparison (multiplying through by $q q_n$ and using $q_n \le q$ ) forces $1 < q_n/(2q) + 1$ , a contradiction once the strict inequalities are tracked. Hence $p/q$ must be a convergent. $\blacksquare$

∎

ProofThe

\le 1/q_n^2

bound — Equation 6

Step 1. Use the tail representation: writing $x_{n+1} = [a_{n+1}; a_{n+2}, \dots]$ (the complete quotient), the algorithm gives exactly

11

\quad x = \frac{x_{n+1} p_n + p_{n-1}}{x_{n+1} q_n + q_{n-1}}.

Derivation hint: apply [3] with the real value $x_{n+1}$ in place of an integer $a_{n+1}$ ; this is the same matrix recurrence evaluated at a real partial quotient.

Step 2. Subtract $p_n/q_n$ and clear denominators:

12

\quad x - \frac{p_n}{q_n} = \frac{(p_n q_{n-1}-p_{n-1}q_n)\,(-1)}{q_n(x_{n+1}q_n + q_{n-1})} = \frac{(-1)^n}{q_n(x_{n+1}q_n + q_{n-1})}.

Derivation hint: combine [11] over common denominator $q_n$ , simplify the numerator using the determinant identity [4].

Step 3. Since $x_{n+1} > a_{n+1} \ge 1$ , the denominator exceeds $q_n(q_n + q_{n-1}) \ge q_n \cdot q_n$ (in fact $x_{n+1}q_n + q_{n-1} > q_{n+1}$ ), giving the upper bound $1/(q_n q_{n+1}) \le 1/q_n^2$ . The lower bound follows since $x_{n+1} < a_{n+1}+1$ implies the denominator $< q_n(q_{n+1}+q_n)$ . $\blacksquare$

∎

mathematician · Aleksandr Khinchin | 1894–1959

Khinchin transformed continued fractions from a computational curiosity into a branch of metric number theory — the study of properties holding for almost all reals in the Lebesgue sense. His 1935 monograph Continued Fractions proved that for almost every $x$ the geometric mean of the partial quotients $\sqrt[n]{a_1 a_2 \cdots a_n}$ converges to a universal constant $K_0$ , independent of $x$ , and established the ergodicity of the Gauss map $G(x) = \{1/x\}$ with respect to the Gauss measure $d\mu = \frac{1}{\ln 2}\frac{dx}{1+x}$ . His work bridged probability theory (he proved the law of the iterated logarithm) and arithmetic, showing the continued fraction algorithm is a measure-preserving dynamical system. The Gauss–Kuzmin–Wirsing operator governing the convergence rate is named partly for his program.

🧠 Intuition

Picture the Stern–Brocot tree or the Farey sequence: rationals organized by denominator. To approximate $x$ , you descend the tree, at each node turning left (toward smaller) or right (toward larger). The partial quotients $a_n$ count how many consecutive turns in the same direction you make before $x$ forces you to switch. A large $a_n$ means $x$ sits very near a "shelf" — a low-denominator rational that approximates it well, so you can stay close for a long time before refining. This is why $\pi = [3;7,15,1,292,\dots]$ has the famous $355/113$ approximation: the partial quotient $292$ is enormous, so $355/113$ (the convergent just before that big jump) is spectacularly accurate. Conversely, $\varphi = [1;1,1,1,\dots]$ has the smallest possible partial quotients everywhere, so it is the hardest number to approximate — the convergents improve as slowly as the theory permits. Geometrically (the Klein/Lagrange picture), the convergents are the lattice points closest to the line $y = x$ in $\mathbb{Z}^2$ , alternating above and below; the partial quotients record how the line cuts successive cells of the integer lattice.

Figure

Convergents straddling the target

x

with shrinking error windows

```svg

```

ExampleContinued fraction of

\sqrt{2}

and its convergents

Given: $x = \sqrt 2 \approx 1.41421356$ .

Step 1 — run the algorithm. $a_0 = \lfloor\sqrt2\rfloor = 1$ ; $x_1 = 1/(\sqrt2 - 1) = \sqrt2 + 1 \approx 2.4142$ . Then $a_1 = 2$ , $x_2 = 1/(x_1 - 2) = 1/(\sqrt2 - 1) = \sqrt2 + 1$ . The process now repeats: $\sqrt 2 = [1; 2,2,2,\dots] = [1;\overline 2]$ (purely periodic tail — this is a quadratic irrational, by Lagrange's theorem).

Step 2 — build convergents via [3]. With $a = (1,2,2,2,2)$ :

$n$	$a_n$	$p_n$	$q_n$	$p_n/q_n$
0	1	1	1	$1.0000$
1	2	3	2	$1.5000$
2	2	7	5	$1.4000$
3	2	17	12	$1.41\overline{6}$
4	2	41	29	$1.413793$

Step 3 — check error bound [6]. For $n=4$ : $|{\sqrt2} - 41/29| \approx 4.20\times10^{-4}$ , while $1/q_4^2 = 1/841 \approx 1.19\times10^{-3}$ . Indeed the error is below the bound.

\boxed{\sqrt 2 = [1;\overline{2}], \quad \frac{p_4}{q_4} = \frac{41}{29}, \quad \left|\sqrt2 - \tfrac{41}{29}\right| \approx 4.2\times10^{-4}}

(Note: $p_n, q_n$ here solve Pell's equation $p^2 - 2q^2 = \pm1$ , e.g. $41^2 - 2\cdot29^2 = 1681 - 1682 = -1$ .)

ExampleWhy

355/113

approximates

\pi

so well

Given: $\pi = [3; 7, 15, 1, 292, 1, 1, \dots]$ .

Step 1 — first few convergents.

$[3] = 3/1$
$[3;7] = 22/7 \approx 3.142857$ (error $\approx 1.26\times10^{-3}$ )
$[3;7,15] = 333/106 \approx 3.141509$ (error $\approx 8.3\times10^{-5}$ )
$[3;7,15,1] = 355/113 \approx 3.1415929$ (error $\approx 2.67\times10^{-7}$ )

Step 2 — explain the jump. The next partial quotient is $a_4 = 292$ (very large). By [6], $|\pi - 355/113| < 1/(q_3 q_4)$ with $q_3 = 113$ and $q_4 = a_4 q_3 + q_2 = 292\cdot113 + 106 = 33102$ . So the error is below $1/(113 \cdot 33102) \approx 2.67\times10^{-7}$ — an error one would naively expect only from a five-digit denominator, achieved with a three-digit one.

Step 3 — verify the best-approximation strength. Compare $1/(2q^2) = 1/(2\cdot113^2) \approx 3.9\times10^{-5}$ . Since the actual error $2.67\times10^{-7} < 3.9\times10^{-5}$ , equation [7] confirms $355/113$ must be a convergent — consistent.

\boxed{\frac{355}{113} \approx \pi \text{ to } 6 \text{ decimal places; the large } a_4 = 292 \text{ is the cause}}

⚠️ Common mistake

Convergents are not the only good approximations, but they bracket them. Between consecutive convergents lie the intermediate (semi-)convergents $\frac{p_{n-1} + k\,p_n}{q_{n-1} + k\,q_n}$ for $1 \le k < a_{n+1}$ . These can be best approximations of the first kind (minimizing $|x - p/q|$ ) without being convergents. Do not assume every excellent rational approximation appears in the convergent list — only the best approximations of the second kind (minimizing $|qx-p|$ ) are exactly the convergents.

⚠️ Common mistake

The bound [7] is sufficient but not necessary. A fraction can be a convergent yet fail $|x - p/q| < 1/(2q^2)$ — e.g. when the next partial quotient is $1$ , a convergent may only achieve $\approx 1/q^2$ , not $1/2q^2$ . Equation [7] guarantees "convergent $\Rightarrow$ good" in reverse direction only: good $\Rightarrow$ convergent.

CounterexampleNot every quadratic irrational is "badly approximable" trivially

One might guess that purely periodic continued fractions correspond exactly to "simple" numbers. But consider $x = [\overline{1,2}] = \frac{\sqrt 3 - 1}{1}\cdot\dots$ — its partial quotients are bounded ( $\le 2$ ), so it is badly approximable (bounded partial quotients $\iff$ $x$ avoids approximation better than $c/q^2$ ). Yet $e = [2;1,2,1,1,4,1,1,6,\dots]$ has unbounded partial quotients (the $2k$ terms grow), so $e$ is not badly approximable despite being a "natural" constant — it admits infinitely many approximations far better than $\varphi$ allows. The lesson: approximability is governed by partial quotient growth, not by how "famous" or "algebraic-looking" the number is.

connection

Continued fractions sit at a crossroads of analysis, algebra, and dynamics. Lagrange's theorem ties them to Quadratic Irrationals: $x$ has an eventually periodic continued fraction iff $x$ is a quadratic irrational, linking the theory to Pell's Equation and the units of real quadratic fields. The Gauss map $G(x) = \{1/x\}$ realizes the shift on partial quotients as a chaotic ergodic dynamical system, placing continued fractions inside Symbolic Dynamics. The approximation hierarchy generalizes through Diophantine Approximation to Liouville's theorem (algebraic numbers of degree $d$ resist approximation beyond exponent $d$ ) and its deep refinement, the Thue–Siegel–Roth Theorem (algebraic irrationals have approximation exponent exactly $2$ ). The metric theory connects to Hausdorff Dimension via the dimensions of sets with prescribed partial-quotient growth, and to Continued Fraction Transformation / transfer operators. Finally, the modular group $\mathrm{SL}_2(\mathbb{Z})$ acting on the hyperbolic plane geometrizes the whole subject: convergents are cusps of geodesics, tying continued fractions to Hyperbolic Geometry and Modular Forms.

🔬 Where this appears

⏳ History

- c. 300 BCE — Euclid. The Euclidean algorithm for GCDs is implicitly the terminating continued fraction algorithm for rationals.

- 499 CE — Aryabhata. Used a method (kuttaka) equivalent to continued fractions to solve linear Diophantine equations.

- 1572 — Bombelli. Approximated

\sqrt{13}

with what amounts to a continued fraction.

- 1655–1695 — Wallis & Brouncker. Brouncker gave the celebrated continued fraction for

4/\pi

; Wallis coined "continued fraction" and proved early recurrence relations in his Arithmetica Infinitorum.

- 1737–1748 — Euler. Proved

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

, established the recurrence [3], and showed periodic continued fractions give quadratic irrationals (one direction of Lagrange's theorem).

- 1768–1770 — Lagrange. Proved the converse: every quadratic irrational has an eventually periodic continued fraction. Applied the method to Pell's equation and to bounding roots of polynomials.

- 1813 — Gauss. Discovered the invariant measure

\frac{1}{\ln 2}\frac{dx}{1+x}

for the Gauss map and posed (in a letter to Laplace) the Gauss–Kuzmin problem on the distribution of partial quotients.

- 1844 — Liouville. Used continued fractions / approximation exponents to construct the first explicit transcendental numbers, proving algebraic numbers cannot be too well approximated.

- 1891 — Hurwitz. Proved the optimal constant

\sqrt5

(equation [8]) and identified the golden ratio as the extremal case.

- 1928–1935 — Kuzmin, Lévy, Khinchin. Kuzmin proved Gauss's conjecture with an error term; Khinchin established the universal constant

K_0

and ergodicity; Lévy found the a.e. growth rate

q_n^{1/n} \to e^{\pi^2/(12\ln 2)}

.

- 1955 — Roth. Proved the Thue–Siegel–Roth theorem (Fields Medal 1958): algebraic irrationals have approximation exponent exactly

2

, the sharpest possible refinement of Liouville, sharp because of Hurwitz.

open-problem

Deep questions remain about the partial quotients of specific natural constants. It is unknown whether the partial quotients of $\pi$ , $e^{2/3}$ wait— $e$ 's pattern is known, but for $\pi$ , $\gamma$ (Euler–Mascheroni), $\sqrt[3]{2}$ , and almost all algebraic numbers of degree $\ge 3$ , it is conjectured but unproven that the partial quotients are unbounded (i.e. these numbers are not badly approximable). The Zaremba conjecture asks whether for some absolute bound $B$ , every integer $q$ is the denominator of a fraction whose continued fraction has all partial quotients $\le B$ — proven only for density-one sets of $q$ (Bourgain–Kontorovich, 2014). The Littlewood conjecture on simultaneous approximation, $\liminf_{q\to\infty} q\,\|q\alpha\|\,\|q\beta\| = 0$ for all $\alpha,\beta$ , is intimately connected to continued fractions of $\alpha,\beta$ and remains open despite the Einstein–Katok–Lindenstrauss measure-rigidity progress showing the exceptional set has Hausdorff dimension zero. Finally, whether Khinchin's constant $K_0$ is itself "normal" or even irrational is unknown — a striking gap, since $K_0$ governs almost every number yet resists analysis as an individual constant.

Continued Fractions and Diophantine Approximation

Formal Statement

Why It Holds

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also