Continued fractions: how to find the best rational approximation to any number

Continued fractions are the Euclidean algorithm in disguise. We develop convergents and the best-approximation property, compute the continued fraction of sqrt(2), connect it to Pell's equation, and sketch the Stern-Brocot tree.

Folio Official

March 1, 2026

The fraction $22/7 = 3.142 \dots$ approximates $π \approx 3.14159 \dots$ with an error of less than $0.04%$ , using a denominator of only $7$ . Why is $22/7$ so good? The answer lies in the theory of continued fractions.

1 Definition

Definition 1 (Continued fraction).

The (simple) continued fraction expansion of a real number

α

is the expression

α = a_{0} + \frac{1}{a _{1} + \frac{1}{a _{2} + \frac{1}{a _{3} + \dots}}}

where

a_{0} \in Z

and

a_{1}, a_{2}, \dots \in Z_{> 0}

are called the partial quotients. We write

α = [a_{0}; a_{1}, a_{2}, a_{3}, \dots]

Example 2.

3.245 = 3 + 0.245 = 3 + 1/ (4 + 1/ (12 + 1/4))

, so

3.245 = [3; 4, 12, 4]

2 The connection to the Euclidean algorithm

The continued fraction expansion and the Euclidean algorithm are exactly the same computation.

Example 3.

The Euclidean algorithm applied to

g cd (47, 13)

$47 = 3 \times 13 + 8$
$13 = 1 \times 8 + 5$
$8 = 1 \times 5 + 3$
$5 = 1 \times 3 + 2$
$3 = 1 \times 2 + 1$
$2 = 2 \times 1 + 0$

The sequence of quotients is

3, 1, 1, 1, 1, 2

. Meanwhile,

47/13 = [3; 1, 1, 1, 1, 2]

. The quotients produced by the Euclidean algorithm are precisely the partial quotients of the continued fraction.

Remark 4.

The continued fraction expansion of a rational number is finite; that of an irrational number is infinite. This mirrors the fact that the Euclidean algorithm terminates in finitely many steps for rational inputs (when the remainder reaches

0

3 Convergents: truncating for good approximations

Definition 5 (Convergent).

The

n

-th convergent of the continued fraction

α = [a_{0}; a_{1}, a_{2}, \dots]

\frac{p _{n}}{q _{n}} = [a_{0}; a_{1}, a_{2}, \dots, a_{n}] .

Convergents can be computed efficiently via a recurrence.

Theorem 6 (Convergent recurrence).

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_{- 2} = 0

q_{- 1} = 0

q_{- 2} = 1

Theorem 7 (Determinant identity).

p_{n} q_{n - 1} - p_{n - 1} q_{n} = (- 1)^{n - 1} .

Remark 8.

This identity implies that the difference between consecutive convergents

p_{n} / q_{n}

and

p_{n - 1} / q_{n - 1}

\pm 1/ (q_{n} q_{n - 1})

. Since

q_{n}

is strictly increasing, the differences shrink rapidly and the convergents approach

α

at great speed.

4 Best rational approximations

Theorem 9 (Best approximation property).

p_{n} / q_{n}

is the

n

-th convergent of

α

, then for any fraction

a / b

with

b \leq q_{n}

and

a / b \neq = p_{n} / q_{n}

α - \frac{p _{n}}{q _{n}} < α - \frac{a}{b} .

Remark 10.

In other words, each convergent is the fraction closest to

α

among all fractions whose denominator does not exceed

q_{n}

. The reason

22/7

approximates

π

so well is that it is the first convergent of

π = [3; 7, 15, 1, 292, \dots]

5 The continued fraction of $2$

Example 11 (Continued fraction of

2

2 = 1 + (2 - 1)

. Since

2 - 1 = 1/ (2 + 1)

2 = 1 + \frac{1}{2 + 1} = 1 + \frac{1}{2 + ( 2 - 1 )} = 1 + \frac{1}{2 + \frac{1}{2 + 1}} .

The pattern repeats:

2 = [1; \overline{2}]

(the partial quotient

2

repeats indefinitely).

The convergents are

1/1, 3/2, 7/5, 17/12, 41/29, \dots

The convergent

17/12 = 1.41 \overline{6}

is an excellent approximation to

2 = 1.41421 \dots

Remark 12.

More generally, for any positive integer

D

that is not a perfect square, the continued fraction expansion of

D

is eventually periodic. This is Lagrange's theorem: quadratic irrationals correspond bijectively to periodic continued fractions.

6 Pell's equation

The continued fraction of $D$ leads directly to solutions of Pell's equation.

Definition 13 (Pell's equation).

For a positive integer

D

(not a perfect square),

x^{2} - D y^{2} = 1

is called Pell's equation.

Theorem 14.

The smallest positive solution

(x_{1}, y_{1})

x^{2} - D y^{2} = 1

is given by the convergent

p_{k} / q_{k}

just before the period of the continued fraction of

D

repeats:

(x_{1}, y_{1}) = (p_{k}, q_{k})

Example 15.

D = 2

2 = [1; \overline{2}]

, with period length

1

. The convergent

p_{0} / q_{0} = 1/1

gives

(x, y) = (1, 1)

1 - 2 = - 1

(wrong sign). The next convergent

p_{1} / q_{1} = 3/2

gives

(x, y) = (3, 2)

9 - 8 = 1

. This is the fundamental solution.

7 The Stern–Brocot tree

Definition 16 (Stern–Brocot tree).

Starting from

0/1

and

1/0

, the Stern–Brocot tree is constructed by repeatedly inserting the mediant

\frac{a + c}{b + d}

between adjacent fractions

a / b

and

c / d

Remark 17.

The Stern–Brocot tree has remarkable properties:

Every positive rational number appears exactly once, in lowest terms.
The tree is always sorted (left child $<$ parent $<$ right child).
The path to each node (a sequence of left and right turns) corresponds to the continued fraction expansion.
A binary search on the tree finds the closest fraction with denominator $\leq N$ in $O (lo g N)$ time.

8 Takeaway

Continued fractions are the Euclidean algorithm viewed from a different angle.
Convergents are the best rational approximations with bounded denominator.
The continued fraction of $D$ is periodic and yields solutions to Pell's equation.
The Stern–Brocot tree organizes all positive rationals into a single systematic structure.

In the final article of this series, we shall see how the theorems developed throughout these eight articles converge in a single, celebrated application: the RSA cryptosystem.

Number Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Continued fractions: how to find the best rational approximation to any number

Folio Official

March 1, 2026

1 Definition

Definition 1 (Continued fraction).

The (simple) continued fraction expansion of a real number

α

is the expression

α = a_{0} + \frac{1}{a _{1} + \frac{1}{a _{2} + \frac{1}{a _{3} + \dots}}}

where

a_{0} \in Z

and

a_{1}, a_{2}, \dots \in Z_{> 0}

are called the partial quotients. We write

α = [a_{0}; a_{1}, a_{2}, a_{3}, \dots]

Example 2.

3.245 = 3 + 0.245 = 3 + 1/ (4 + 1/ (12 + 1/4))

, so

3.245 = [3; 4, 12, 4]

2 The connection to the Euclidean algorithm

The continued fraction expansion and the Euclidean algorithm are exactly the same computation.

Example 3.

The Euclidean algorithm applied to

g cd (47, 13)

$47 = 3 \times 13 + 8$
$13 = 1 \times 8 + 5$
$8 = 1 \times 5 + 3$
$5 = 1 \times 3 + 2$
$3 = 1 \times 2 + 1$
$2 = 2 \times 1 + 0$

The sequence of quotients is

3, 1, 1, 1, 1, 2

. Meanwhile,

47/13 = [3; 1, 1, 1, 1, 2]

. The quotients produced by the Euclidean algorithm are precisely the partial quotients of the continued fraction.

Remark 4.

0

3 Convergents: truncating for good approximations

Definition 5 (Convergent).

The

n

-th convergent of the continued fraction

α = [a_{0}; a_{1}, a_{2}, \dots]

\frac{p _{n}}{q _{n}} = [a_{0}; a_{1}, a_{2}, \dots, a_{n}] .

Convergents can be computed efficiently via a recurrence.

Theorem 6 (Convergent recurrence).

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_{- 2} = 0

q_{- 1} = 0

q_{- 2} = 1

Theorem 7 (Determinant identity).

p_{n} q_{n - 1} - p_{n - 1} q_{n} = (- 1)^{n - 1} .

Remark 8.

This identity implies that the difference between consecutive convergents

p_{n} / q_{n}

and

p_{n - 1} / q_{n - 1}

\pm 1/ (q_{n} q_{n - 1})

. Since

q_{n}

is strictly increasing, the differences shrink rapidly and the convergents approach

α

at great speed.

4 Best rational approximations

Theorem 9 (Best approximation property).

p_{n} / q_{n}

is the

n

-th convergent of

α

, then for any fraction

a / b

with

b \leq q_{n}

and

a / b \neq = p_{n} / q_{n}

α - \frac{p _{n}}{q _{n}} < α - \frac{a}{b} .

Remark 10.

In other words, each convergent is the fraction closest to

α

among all fractions whose denominator does not exceed

q_{n}

. The reason

22/7

approximates

π

so well is that it is the first convergent of

π = [3; 7, 15, 1, 292, \dots]

5 The continued fraction of $2$

Example 11 (Continued fraction of

2

2 = 1 + (2 - 1)

. Since

2 - 1 = 1/ (2 + 1)

2 = 1 + \frac{1}{2 + 1} = 1 + \frac{1}{2 + ( 2 - 1 )} = 1 + \frac{1}{2 + \frac{1}{2 + 1}} .

The pattern repeats:

2 = [1; \overline{2}]

(the partial quotient

2

repeats indefinitely).

The convergents are

1/1, 3/2, 7/5, 17/12, 41/29, \dots

The convergent

17/12 = 1.41 \overline{6}

is an excellent approximation to

2 = 1.41421 \dots

Remark 12.

More generally, for any positive integer

D

that is not a perfect square, the continued fraction expansion of

D

is eventually periodic. This is Lagrange's theorem: quadratic irrationals correspond bijectively to periodic continued fractions.

6 Pell's equation

The continued fraction of $D$ leads directly to solutions of Pell's equation.

Definition 13 (Pell's equation).

For a positive integer

D

(not a perfect square),

x^{2} - D y^{2} = 1

is called Pell's equation.

Theorem 14.

The smallest positive solution

(x_{1}, y_{1})

x^{2} - D y^{2} = 1

is given by the convergent

p_{k} / q_{k}

just before the period of the continued fraction of

D

repeats:

(x_{1}, y_{1}) = (p_{k}, q_{k})

Example 15.

D = 2

2 = [1; \overline{2}]

, with period length

1

. The convergent

p_{0} / q_{0} = 1/1

gives

(x, y) = (1, 1)

1 - 2 = - 1

(wrong sign). The next convergent

p_{1} / q_{1} = 3/2

gives

(x, y) = (3, 2)

9 - 8 = 1

. This is the fundamental solution.

7 The Stern–Brocot tree

Definition 16 (Stern–Brocot tree).

Starting from

0/1

and

1/0

, the Stern–Brocot tree is constructed by repeatedly inserting the mediant

\frac{a + c}{b + d}

between adjacent fractions

a / b

and

c / d

Remark 17.

The Stern–Brocot tree has remarkable properties:

Every positive rational number appears exactly once, in lowest terms.
The tree is always sorted (left child $<$ parent $<$ right child).
The path to each node (a sequence of left and right turns) corresponds to the continued fraction expansion.
A binary search on the tree finds the closest fraction with denominator $\leq N$ in $O (lo g N)$ time.

8 Takeaway

Continued fractions are the Euclidean algorithm viewed from a different angle.
Convergents are the best rational approximations with bounded denominator.
The continued fraction of $D$ is periodic and yields solutions to Pell's equation.
The Stern–Brocot tree organizes all positive rationals into a single systematic structure.

In the final article of this series, we shall see how the theorems developed throughout these eight articles converge in a single, celebrated application: the RSA cryptosystem.

Number Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Continued fractions: how to find the best rational approximation to any number

1 Definition

2 The connection to the Euclidean algorithm

3 Convergents: truncating for good approximations

4 Best rational approximations

5 The continued fraction of $2$

6 Pell's equation

7 The Stern–Brocot tree

8 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

Continued fractions: how to find the best rational approximation to any number

1 Definition

2 The connection to the Euclidean algorithm

3 Convergents: truncating for good approximations

4 Best rational approximations

5 The continued fraction of $2$

6 Pell's equation

7 The Stern–Brocot tree

8 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

1 Definition

2 The connection to the Euclidean algorithm

3 Convergents: truncating for good approximations

4 Best rational approximations

5 The continued fraction of2​

6 Pell's equation

7 The Stern–Brocot tree

8 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

1 Definition

2 The connection to the Euclidean algorithm

3 Convergents: truncating for good approximations

4 Best rational approximations

5 The continued fraction of2​

6 Pell's equation

7 The Stern–Brocot tree

8 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

5 The continued fraction of $2$

5 The continued fraction of $2$