Continued Fractions, an Honest Introduction

A continued fraction is the Euclidean algorithm written backwards, but the consequences are wild: a sharp constant in Diophantine approximation, eventual periodicity exactly at the quadratic irrationals, and a chaotic shift map whose invariant density Gauss guessed in a letter to Laplace in 1812.

The Euclidean algorithm, turned inside out

Start with something concrete. Take $\frac{45}{16}$. Divide with remainder: $45 = 2 \cdot 16 + 13$, so $\frac{45}{16} = 2 + \frac{13}{16}$. Now flip the fractional part upside down and repeat. $\frac{16}{13} = 1 + \frac{3}{13}$; then $\frac{13}{3} = 4 + \frac{1}{3}$. Stacking those steps gives

The semicolon separates the integer part from the rest. For an irrational the process never terminates, but each step is mechanical. Let $x_0 = x$ and define

In words: write down the floor, take the reciprocal of what's left over, repeat. Here $a_n$ is the $n$-th partial quotient; the whole sequence $[a_0;\, a_1, a_2, \ldots]$ is the simple continued fraction of $x$. Try $x = \sqrt 2$: $a_0 = 1$, $x_1 = 1/(\sqrt 2 - 1) = \sqrt 2 + 1$, so $a_1 = 2$ and $x_2 = 1/(\sqrt 2 - 1) = x_1$. The expansion locks into $[1; 2, 2, 2, \ldots]$ forever.

Convergents and the magic identity

Truncate after $n$ steps and you get a rational $p_n/q_n$, the $n$-th convergent. You don't have to re-do the nested division each time; there's a two-term recursion. Initialize $p_{-1} = 1$, $q_{-1} = 0$, $p_0 = a_0$, $q_0 = 1$, and for $n \geq 1$

Here $p_n$ is the numerator and $q_n$ the denominator of the $n$-th truncation; the formula says each is a linear combination of the previous two, weighted by the current digit. For $\pi = [3;\, 7, 15, 1, 292, \ldots]$:

• $p_0/q_0 = 3/1$,
• $p_1/q_1 = 22/7 \approx 3.1429$,
• $p_2/q_2 = 333/106 \approx 3.14151$,
• $p_3/q_3 = 355/113 \approx 3.1415929$,
• $p_4/q_4 = 103993/33102 \approx 3.14159265301$.

That huge $a_4 = 292$ is why 355/113 is so unreasonably good: a large next digit means the current convergent has to stay close for a long stretch.

The entire theory hangs on a single identity. Multiply the two recursions, subtract, telescope, and you find

This is the load-bearing line of the whole subject. Read it: the determinant of any two consecutive convergents is $\pm 1$. So $\gcd(p_n, q_n) = 1$ (no hidden simplification — convergents are always in lowest terms), and the difference between neighbors is

The $q_n$ grow at least as fast as Fibonacci numbers (since $a_n \geq 1$ gives $q_n \geq q_{n-1} + q_{n-2}$), so the gap shrinks exponentially while alternating in sign. The convergents pinch in on $x$ from both sides.

How well do they approximate?

A direct corollary of the identity: every convergent satisfies

So you get accuracy $1/q^2$ for free, with a bonus inversely proportional to the next digit. Dirichlet's theorem promises infinitely many such rationals exist; continued fractions hand you a specific list.

The sharp version is Hurwitz's theorem (1891): for every irrational $x$ there are infinitely many rationals $p/q$ with

and the constant $\sqrt 5$ cannot be improved. The worst-case irrational — the one hardest to approximate — is the golden ratio $\varphi = [1; 1, 1, 1, \ldots]$. Its partial quotients are all the minimum value 1, so its $q_n$ grow as slowly as possible (literally the Fibonacci sequence), and the bound is exactly saturated. Any irrational whose expansion ends in all 1s (equivalent to $\varphi$ under a Möbius transformation over $\mathbb Z$) is equally bad; everything else can be approximated strictly better than $1/(\sqrt 5\, q^2)$, with the next value $\sqrt 8$ (the second-hardest case, attained by $\sqrt 2$ and its relatives, whose expansions end in all 2s) and a Lagrange spectrum of admissible constants accumulating at $3$.

What makes convergents special is not just the rate. They are best approximations in a strong sense: if $0 < q' \leq q_n$ and $p'/q' \neq p_n/q_n$, then

No rational with a smaller denominator does better; everything else is wasting denominator.

Periodicity and quadratic irrationals

For $\sqrt 2$ the expansion was eventually periodic. Lagrange (1770) characterized this exactly: $x$ has an eventually periodic simple continued fraction iff $x$ is a quadratic irrational (a root of an irreducible quadratic over $\mathbb Q$). The easy direction — periodic CF $\Rightarrow$ quadratic irrational — is Euler's (1737); Lagrange's contribution was the hard converse, quadratic irrational $\Rightarrow$ periodic.

The "if" direction is the interesting one. Define the $n$-th complete quotient $\alpha_n = [a_n;\, a_{n+1}, a_{n+2}, \ldots]$, the tail starting at step $n$. A short calculation with the recursion gives the exact Möbius identity

Now suppose $x$ satisfies $A x^2 + B x + C = 0$ with $A, B, C \in \mathbb Z$. Substituting the formula above and clearing denominators shows $\alpha_n$ satisfies a quadratic $A_n \alpha^2 + B_n \alpha + C_n = 0$ with integer coefficients, and with discriminant $B_n^2 - 4 A_n C_n = B^2 - 4AC$ — the discriminant is invariant. A separate computation bounds $|A_n|, |B_n|, |C_n|$ in terms of the discriminant and the $q_n$, but the key step is invariance: finitely many integer triples have a given discriminant inside a bounded box, so by pigeonhole two complete quotients $\alpha_m = \alpha_n$ must coincide. From that point on the expansion repeats. The other direction (Euler's) is one line: a periodic CF satisfies $\alpha = (a \alpha + b)/(c \alpha + d)$ for fixed integers, which is a quadratic in $\alpha$.

So $\sqrt 7 = [2;\, \overline{1, 1, 1, 4}]$ (the bar marks the period), and the Pell equation $X^2 - 7 Y^2 = 1$ has its solutions hiding in the convergents at the period boundaries. This is how Bhāskara II solved $61 X^2 + 1 = Y^2$ in the 12th century — the convergents of $\sqrt{61}$ deliver the minimal solution with $Y \approx 1.77 \times 10^9$.

The Gauss map and statistical chaos

Now the deeper picture. Define the Gauss map on $[0, 1)$:

In words: take the reciprocal and drop the integer part. This is the continued-fraction algorithm packaged as a dynamical system: if $x = [0;\, a_1, a_2, \ldots]$, then $T(x) = [0;\, a_2, a_3, \ldots]$ and $a_n = \lfloor 1/T^{n-1}(x) \rfloor$.

The map is wildly expanding — its slope is $|T'(x)| = 1/x^2$, which blows up near zero — and it looks chaotic. But Gauss noticed that it has an explicit invariant probability density:

Here $\rho$ is a density on $[0,1]$ (it integrates to 1: $\int_0^1 \frac{dx}{(1+x) \ln 2} = 1$), and "invariant" means that if $X$ has density $\rho$ then $T(X)$ has density $\rho$ as well. You can verify it by the change-of-variables formula summed over the countably many branches $T^{-1}$ has.

The Gauss map together with $\rho$ is ergodic (one can prove this with a Knopp-style argument on cylinder sets), so Birkhoff's theorem applies: for Lebesgue-almost-every irrational $x$ in $[0,1]$, time averages of any $L^1$ observable equal space averages against $\rho$. Plug in the indicator of "partial quotient equals $k$" and you get the Gauss–Kuzmin theorem: for almost every $x$,

A "1" appears with limiting frequency $\log_2(4/3) \approx 41.5\%$, a "2" with $\approx 17\%$, a "3" with $\approx 9.3\%$. Kuzmin (1928) gave a rate of convergence; Lévy improved it; Wirsing (1974) found the optimal exponential rate $\lambda \approx 0.30366\ldots$ — the Gauss–Kuzmin–Wirsing constant, the second eigenvalue of the transfer operator. Khinchin (1935) showed the geometric mean $(a_1 a_2 \cdots a_n)^{1/n}$ converges, for almost every $x$, to Khinchin's constant

independent of $x$. And for almost every $x$ the denominators themselves grow at a universal rate: $\frac{1}{n}\ln q_n \to \frac{\pi^2}{12 \ln 2}$ (Lévy's constant), pinning down the typical speed of convergence.

What you actually know now

To be honest about what was earned versus what was asserted:

• Proved here in full: every rational has a (essentially unique) finite CF; the $p_n, q_n$ recursion; the determinant identity $p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}$ and the $1/(q_n q_{n+1})$ approximation bound. These are mechanical from the definitions.
• Sketched: best approximation; Lagrange's periodicity theorem (the load-bearing step was discriminant invariance plus pigeonhole on integer triples).
• Stated only: Hurwitz with the sharp $\sqrt 5$ (the proof is elementary but case-bashy, via three consecutive convergents); Khinchin's constant and Gauss–Kuzmin–Wirsing rates (genuine proofs use transfer operators on Banach spaces of analytic functions — a different essay).
• Open: whether the CF expansion of any specific famous irrational is statistically generic. We do not know if the partial quotients of $\pi$ are bounded, normal, or anything. For $e$ we got lucky — Euler showed $e = [2;\, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, \ldots]$, so $e$ is provably not Gauss–Kuzmin normal — but it's about the only natural constant for which we can answer.

The honest framing: continued fractions are the right coordinate system on the irrationals when you care about rational approximation, and the right coordinate system on a chaotic dynamical system whose invariant measure is elementary. The fact that those two viewpoints are the same viewpoint is the punchline of the whole theory.