Continued Fractions

Introduction

When we approximate π by 22/7 or 355/113 we are using remarkably good rational approximations to an irrational number. These approximations do not arise by accident—they come from the theory of continued fractions, one of the most elegant and powerful tools in number theory.

A continued fraction represents a number as a sequence of integer quotients obtained through repeated division. Unlike decimal expansions, continued fractions provide optimal rational approximations at each step. They reveal the arithmetic structure of real numbers in ways that decimals cannot, showing why some irrationals (like the golden ratio) are harder to approximate by rationals than others.

Continued fractions connect to the Euclidean algorithm, Diophantine equations, Pell equations, and the theory of quadratic irrationals. They appear in calendar calculations, gear ratios, musical tuning systems, and the analysis of algorithms. Understanding continued fractions means understanding the deepest properties of rational approximation.

Formal Definition

A simple continued fraction is an expression of the form:

(a_0)+1/((a_1)+1/((a_2)+1/((a_3)+1/⋱)))

where (a_0) is an integer (possibly negative or zero) and (a_1),(a_2),(a_3),… are positive integers called the partial quotients. We use the compact notation:

[(a_0);(a_1),(a_2),(a_3),…]

For a finite continued fraction [(a_0);(a_1),…,(a_n)] the expression terminates and represents a rational number. For an infinite continued fraction [(a_0);(a_1),(a_2),…] the expression continues indefinitely and represents an irrational number.

Computing Continued Fractions

To find the continued fraction expansion of a positive real number x we use an iterative process. Let (x_0)=x At each step:

(a_n)=⌊(x_n)⌋,(x_n+1)=1/((x_n)−(a_n))

The process terminates when (x_n) is an integer (for rational x or continues forever (for irrational x. This algorithm is equivalent to the Euclidean algorithm when applied to the numerator and denominator of a rational number.

Convergents

The convergents of a continued fraction are the rational numbers obtained by truncating the expansion. The nth convergent is:

(p_n)/(q_n)=[(a_0);(a_1),(a_2),…,(a_n)]

The numerators (p_n) and denominators (q_n) satisfy the recurrence relations:

(p_n)=(a_n)*(p_n−1)+(p_n−2),(q_n)=(a_n)*(q_n−1)+(q_n−2)

with initial values (p_−1)=1,(p_0)=(a_0) and (q_−1)=0,(q_0)=1 These recurrences allow efficient computation of convergents without evaluating nested fractions.

Fundamental Properties

Best Rational Approximations

The convergents of a continued fraction are the best rational approximations in a precise sense. If (p_n)/(q_n) is a convergent to x then for any fraction a/b with 0<b≤(q_n):

|x−(p_n)/(q_n)|≤|x−a/b|

No fraction with smaller or equal denominator can be closer to x This optimality property makes convergents invaluable for approximation problems.

Alternating Approximations

Successive convergents alternate between being less than and greater than the target value. The even convergents (p_0)/(q_0),(p_2)/(q_2),(p_4)/(q_4),… form an increasing sequence approaching x from below, while odd convergents (p_1)/(q_1),(p_3)/(q_3),… decrease toward x from above.

Error Bounds

The error in approximating x by its nth convergent satisfies:

1/((q_n)*((q_n+1)+(q_n)))<|x−(p_n)/(q_n)|<1/((q_n)*(q_n+1))

Since (q_n) grows at least exponentially fast for most numbers, convergents provide extremely accurate approximations.

Worked Examples

Example 1: A Rational Number

Find the continued fraction expansion of 43/19

We apply the algorithm iteratively:

(x_0)=43/19=2.263…⇒(a_0)=2,(x_1)=1/(43/19−2)=19/5

(x_1)=19/5=3.8⇒(a_1)=3,(x_2)=1/(19/5−3)=5/4

(x_2)=5/4=1.25⇒(a_2)=1,(x_3)=1/(5/4−1)=4

(x_3)=4⇒(a_3)=4 (terminates)

Therefore 43/19=[2;3,1,4].

We can verify:
2+1/(3+1/(1+1/4))=2+1/(3+4/5)=2+5/19=43/19.

Example 2: The Golden Ratio

The golden ratio ϕ=(1+√(,5))/2≈1.618 has the remarkable property that ϕ=1+1/ϕ This means:

ϕ=1+1/(1+1/(1+1/(1+⋱)))=[1;1,1,1,…]

All partial quotients equal 1, making ϕ the simplest possible infinite continued fraction. The convergents are ratios of consecutive Fibonacci numbers: 1/1,2/1,3/2,5/3,8/5,… Since the partial quotients are as small as possible, these convergents converge slowly, making ϕ the most poorly approximable irrational number.

Example 3: Square Root of 2

For √(,2)≈1.414 we compute:

(a_0)=1,(x_1)=1/(√(,2)−1)=(√(,2)+1)/1=√(,2)+1≈2.414

(a_1)=2,(x_2)=1/((√(,2)+1)−2)=1/(√(,2)−1)=√(,2)+1

The pattern repeats! Therefore √(,2)=[1;(2)]=[1;2,2,2,…] The convergents 1/1,3/2,7/5,17/12,41/29,… give increasingly accurate approximations. Note that 7/5=1.4 and 17/12≈1.4167

Quadratic Irrationals

A fundamental theorem states that a real number has an eventually periodic continued fraction expansion if and only if it is a quadratic irrational—a root of a quadratic polynomial with integer coefficients. Thus √(,d) for any non-square integer d has a periodic expansion, but π e and √(3,2) do not.

Connection to Other Concepts

The Euclidean algorithm for computing gcd(a,b) is equivalent to computing the continued fraction of a/b The sequence of quotients in the Euclidean algorithm gives exactly the partial quotients of the continued fraction.

Continued fractions provide the complete solution to Pell equations x2−d(y2)=1 The convergents of √(,d) yield all solutions, with the fundamental solution coming from the convergent just before the periodic part repeats.

Dirichlet approximation theorem guarantees that for any irrational α and any N there exists a rational p/q with q≤N such that |α−p/q|<1/(q*N) Continued fractions make this theorem constructive by providing the actual approximations.

Summary

Continued fractions express numbers as nested divisions [(a_0);(a_1),(a_2),…] with integer partial quotients. Rational numbers have finite expansions; irrationals have infinite ones. Quadratic irrationals have eventually periodic expansions.

The convergents (p_n)/(q_n) are computed via the recurrence (p_n)=(a_n)*(p_n−1)+(p_n−2) and provide the best rational approximations with bounded denominators. They alternate above and below the target value, converging rapidly.

Continued fractions unite the Euclidean algorithm, Pell equations, Diophantine approximation, and the theory of quadratic fields. They reveal the arithmetic essence of real numbers in ways that decimal expansions cannot, showing that numbers like ϕ and √(,2) have fundamentally different approximation properties.