Continued Fractions

Definition

Examples

In Depth

A continued fraction expresses a number as \(a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cdots}}\), written \([a_0;a_1,a_2,\ldots]\). Every rational number has a finite continued fraction; every irrational has an infinite one. The convergents \(p_k/q_k\) are the best rational approximations to the number.

The Euclidean algorithm produces the continued fraction expansion: repeatedly take the integer part and invert the remainder. For \(\sqrt{2}=[1;2,2,2,\ldots]\), the convergents \(1/1, 3/2, 7/5, 17/12,\ldots\) are the best rational approximations and satisfy \(p_k^2-2q_k^2=\pm1\) (Pell's equation).

Periodic continued fractions characterize quadratic irrationals (Lagrange's theorem): \(\alpha\) has a periodic continued fraction iff \(\alpha\) satisfies a quadratic equation with integer coefficients. The period length is related to the class number of the associated quadratic field.

The golden ratio \(\phi=[1;1,1,1,\ldots]\) has the simplest possible continued fraction and is the 'most irrational' number — its convergents are ratios of consecutive Fibonacci numbers, and it is hardest to approximate by rationals (Hurwitz's theorem).

Continued fractions are used in the PSLQ algorithm for finding integer relations, in the Stern–Brocot tree for enumerating rationals, and in solving Pell's equation \(x^2-Dy^2=1\). They also appear in the analysis of the Euclidean algorithm's worst-case complexity (Fibonacci inputs).

Key Properties & Applications

The Euclidean algorithm and continued fractions are intimately connected: the quotients in the Euclidean algorithm are exactly the partial quotients of the continued fraction. The number of steps equals the number of partial quotients.

Diophantine approximation: Hurwitz's theorem states that for any irrational \(\alpha\), there are infinitely many rationals \(p/q\) with \(|\alpha-p/q|<1/(\sqrt{5}q^2)\). The constant \(\sqrt{5}\) is best possible (achieved by the golden ratio). The convergents of the continued fraction provide these approximations.

Continued fractions are used in the PSLQ algorithm (integer relation detection), in the analysis of hash functions and pseudorandom number generators, and in the theory of dynamical systems (rotation numbers of circle maps are continued fractions).

Further Reading & Context

The study of continued fractions connects to many areas of mathematics and its applications. Understanding the foundational definitions and theorems provides the basis for advanced work in analysis, algebra, and applied mathematics.

Historical development: most mathematical concepts evolved over centuries, with contributions from mathematicians across many cultures. The modern axiomatic treatment provides rigor, while computational tools enable practical application.

In modern mathematics, this topic appears in graduate courses and research across pure and applied mathematics. Connections to computer science, physics, and engineering make it a versatile and important area of study. Mastery of the core results and techniques opens doors to research in number theory, analysis, geometry, and beyond.

Recommended next steps: work through the standard theorems with full proofs, explore the connections to related topics listed above, and practice with a variety of problems ranging from computational exercises to theoretical proofs. The interplay between different areas of mathematics is one of the subject's greatest rewards.

Deep Dive: Continued Fractions

This lesson extends core ideas for continued fractions with rigorous reasoning, edge-case checks, and application framing in number theory.

Practice Set

References & Editorial Notes

• Stewart, Calculus.
• Strang, Introduction to Linear Algebra.
• Apostol, Mathematical Analysis.

Last editorial review: 2026-04-14.