Euclid's Algorithm and Convergents - Continued Fractions Course

One of the most beautiful structures in all of number theory hides inside a deceptively simple idea: what happens when you keep taking reciprocals? The answer is the theory of continued fractions, and it begins with an algorithm that Euclid described over two thousand years ago.

Convergents approaching the true value

Simple Continued Fractions

Definition (Continued Fraction). A simple continued fraction is an expression of the form

$$ a_0 + \dfrac{1}{\displaystyle a_1 + \dfrac{1}{\displaystyle a_2 + \dfrac{1}{\displaystyle a_3 + \ddots}}} $$

where $ a_0 \in \mathbb{Z} $ and $ a_i \in \mathbb{N} $ for $ i \geq 1 $. We write this compactly as $ [a_0; a_1, a_2, a_3, \ldots] $. The integers $ a_i $ are called the partial quotients.

If the sequence of partial quotients is finite, we call it a finite continued fraction; otherwise it is an infinite continued fraction.

The Euclidean Algorithm Connection

The most natural way continued fractions arise is through the Euclidean algorithm. Given integers $ a > b > 0 $, the algorithm produces:

$$ \begin{aligned} a &= q_0 \cdot b + r_1, \\ b &= q_1 \cdot r_1 + r_2, \\ r_1 &= q_2 \cdot r_2 + r_3, \\ &\;\;\vdots \end{aligned} $$

until we reach a zero remainder. The quotients $ q_0, q_1, q_2, \ldots $ are precisely the partial quotients of $ a/b $.

Example (GCD via Continued Fractions). Let us compute $ \gcd(171, 67) $:

$$ \begin{aligned} 171 &= 2 \cdot 67 + 37, \\ 67 &= 1 \cdot 37 + 30, \\ 37 &= 1 \cdot 30 + 7, \\ 30 &= 4 \cdot 7 + 2, \\ 7 &= 3 \cdot 2 + 1, \\ 2 &= 2 \cdot 1 + 0. \end{aligned} $$

So $ \gcd(171,67) = 1 $ and

$$ \frac{171}{67} = [2; 1, 1, 4, 3, 2] = 2 + \dfrac{1}{\displaystyle 1 + \dfrac{1}{\displaystyle 1 + \dfrac{1}{\displaystyle 4 + \dfrac{1}{\displaystyle 3 + \dfrac{1}{2}}}}} $$

Rationals, Irrationals, and Their Expansions

Theorem (Rational Numbers and Finite CFs). A real number $ \alpha $ is rational if and only if its continued fraction expansion is finite. Moreover, every rational number has exactly two finite CF representations:

$$ [a_0; a_1, \ldots, a_n] = [a_0; a_1, \ldots, a_n – 1, 1] \quad \text{when } a_n > 1. $$

Proof. If $ \alpha = p/q $ with $ q > 0 $, the Euclidean algorithm on $ (p, q) $ terminates in finitely many steps (since remainders strictly decrease), yielding a finite CF. Conversely, a finite CF is built from integer operations and reciprocals, hence represents a rational number. For the two representations, note that $ a_n = (a_n – 1) + 1/1 $.

Theorem (Irrational Numbers and Infinite CFs). Every irrational number $ \alpha $ has a unique infinite continued fraction expansion $ [a_0; a_1, a_2, \ldots] $ obtained by the algorithm: set $ \alpha_0 = \alpha $, and for $ n \geq 0 $,

$$ a_n = \lfloor \alpha_n \rfloor, \quad \alpha_{n+1} = \frac{1}{\alpha_n – a_n}. $$

The sequence $ (\alpha_n) $ consists of the complete quotients. Since $ \alpha $ is irrational, $ \alpha_n – a_n \neq 0 $ for all $ n $, so the process never terminates.

Key Examples

The Golden Ratio. Let $ \varphi = \frac{1+\sqrt{5}}{2} $. Then $ a_0 = 1 $ and

$$ \alpha_1 = \frac{1}{\varphi – 1} = \frac{2}{\sqrt{5}-1} = \frac{\sqrt{5}+1}{2} = \varphi. $$

So $ \alpha_1 = \varphi = \alpha_0 $, giving $ \varphi = [1; 1, 1, 1, \ldots] = [1; \overline{1}] $. The golden ratio has the simplest possible continued fraction: all partial quotients equal to 1.

$ \sqrt{2} $. We have $ \sqrt{2} \approx 1.41421\ldots $, so $ a_0 = 1 $. Then

$$ \alpha_1 = \frac{1}{\sqrt{2} – 1} = \sqrt{2} + 1 \approx 2.41421\ldots $$

so $ a_1 = 2 $, and $ \alpha_2 = 1/(\sqrt{2}-1) = \sqrt{2}+1 = \alpha_1 $. Therefore $ \sqrt{2} = [1; \overline{2}] $.

$ \sqrt{3} $. We have $ a_0 = 1 $, $ \alpha_1 = (\sqrt{3}+1)/2 \approx 1.366 $, so $ a_1 = 1 $, and $ \alpha_2 = \sqrt{3}+1 \approx 2.732 $, so $ a_2 = 2 $, and $ \alpha_3 = \alpha_1 $. Therefore $ \sqrt{3} = [1; \overline{1, 2}] $.

$ \pi $. The continued fraction of $ \pi $ begins

$$ \pi = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, \ldots]. $$

The large partial quotient 292 at position 4 explains why the convergent $ 355/113 = [3; 7, 15, 1] $ is such an excellent approximation to $ \pi $:

$$ \left|\pi – \frac{355}{113}\right| \approx 2.67 \times 10^{-7}, $$

accurate to six decimal places. This approximation was known to the Chinese mathematician Zu Chongzhi in the 5th century.

Tip: The CF algorithm can be summarized as a compact loop: given $ \alpha $, set $ \alpha_0 = \alpha $ and repeat $ a_n = \lfloor \alpha_n \rfloor $, $ \alpha_{n+1} = 1/(\alpha_n – a_n) $. This is equivalent to iterating the Gauss map $ T: x \mapsto \{1/x\} $ on the interval $ (0,1] $.

Convergents and Their Properties

Definition (Convergents). Given a continued fraction $ [a_0; a_1, a_2, \ldots] $, the $ n $th convergent is the finite truncation

$$ c_n = \frac{p_n}{q_n} = [a_0; a_1, a_2, \ldots, a_n]. $$

Theorem (Recurrence Relations). The numerators $ p_n $ and denominators $ q_n $ of the convergents satisfy

$$ \begin{aligned} p_n &= a_n p_{n-1} + p_{n-2}, \\ q_n &= a_n q_{n-1} + q_{n-2}, \end{aligned} $$

with initial values $ p_{-1} = 1 $, $ p_{-2} = 0 $, $ q_{-1} = 0 $, $ q_{-2} = 1 $.

Example (Convergents of $ \sqrt{2} $). With $ \sqrt{2} = [1; 2, 2, 2, \ldots] $, we compute:

$ n $: $ a_n $ | $ -2 $: | $ -1 $: | 0: 1 | 1: 2 | 2: 2 | 3: 2 | 4: 2 | 5: 2
$ n $: $ p_n $ | $ -2 $: 0 | $ -1 $: 1 | 0: 1 | 1: 3 | 2: 7 | 3: 17 | 4: 41 | 5: 99
$ n $: $ q_n $ | $ -2 $: 1 | $ -1 $: 0 | 0: 1 | 1: 2 | 2: 5 | 3: 12 | 4: 29 | 5: 70
$ n $: $ p_n/q_n $ | $ -2 $: | $ -1 $: | 0: 1 | 1: 3/2 | 2: 7/5 | 3: 17/12 | 4: 41/29 | 5: 99/70
The convergents oscillate around $ \sqrt{2} \approx 1.41421 $: $ 1, 1.5, 1.4, 1.4167, 1.4138, 1.4143, \ldots $

The Fundamental Identity

Important: For all $ n \geq 0 $,
$$ > p_n q_{n-1} – p_{n-1} q_n = (-1)^{n-1}. > $$
Equivalently, $ \gcd(p_n, q_n) = 1 $ for every convergent.

Proof. Base case: $ n = 0 $: $ p_0 q_{-1} – p_{-1} q_0 = a_0 \cdot 0 – 1 \cdot 1 = -1 = (-1)^{-1} $.

Inductive step: Assume $ p_{n-1} q_{n-2} – p_{n-2} q_{n-1} = (-1)^{n-2} $. Using the recurrences:

$$ \begin{aligned} p_n q_{n-1} – p_{n-1} q_n &= (a_n p_{n-1} + p_{n-2})q_{n-1} – p_{n-1}(a_n q_{n-1} + q_{n-2})\\ &= -(p_{n-1} q_{n-2} – p_{n-2} q_{n-1})\\ &= -(-1)^{n-2} = (-1)^{n-1}. \quad \square \end{aligned} $$

Corollary. For $ n \geq 1 $,

$$ \frac{p_n}{q_n} – \frac{p_{n-1}}{q_{n-1}} = \frac{(-1)^{n-1}}{q_n q_{n-1}}. $$

Corollary. For $ n \geq 2 $,

$$ \frac{p_n}{q_n} – \frac{p_{n-2}}{q_{n-2}} = \frac{(-1)^n a_n}{q_n q_{n-2}}. $$

Oscillation of Convergents

Theorem. The even-indexed convergents $ c_0, c_2, c_4, \ldots $ form a strictly increasing sequence, the odd-indexed convergents $ c_1, c_3, c_5, \ldots $ form a strictly decreasing sequence, and every even convergent is less than every odd convergent. For an infinite CF with value $ \alpha $:

$$ c_0 < c_2 < c_4 < \cdots < \alpha < \cdots < c_5 < c_3 < c_1. $$

[Image: Plot showing convergents of sqrt(2) alternating above and below the value]

Best Rational Approximations

The convergents of a continued fraction provide the best rational approximations in a very precise sense.

Definition (Best Approximation). A fraction $ p/q $ (with $ q > 0 $) is a best rational approximation to $ \alpha $ if for every fraction $ a/b $ with $ 0 < b \leq q $ and $ a/b \neq p/q $,

$$ |q\alpha – p| < |b\alpha – a|. $$

Important: Every convergent $ p_n/q_n $ of the continued fraction expansion of an irrational $ \alpha $ is a best rational approximation to $ \alpha $. Conversely, every best approximation to $ \alpha $ is a convergent.

The proof proceeds in two steps. First, one shows that $ |q_n \alpha – p_n| < |q_{n-1} \alpha – p_{n-1}| $ for all $ n \geq 1 $, using the exact representation $ \alpha = (p_n \alpha_{n+1} + p_{n-1})/(q_n \alpha_{n+1} + q_{n-1}) $. Then, for any $ a/b $ with $ |b\alpha – a| \leq |q_n \alpha – p_n| $ and $ b \leq q_n $, one uses the fundamental identity to express $ a, b $ as integer combinations of consecutive convergents and derives that $ a/b = p_n/q_n $.

An important consequence: for every convergent $ p_n/q_n $,

$$ \left|\alpha – \frac{p_n}{q_n}\right| < \frac{1}{q_n q_{n+1}} < \frac{1}{q_n^2}. $$

Legendre’s Criterion

Theorem (Legendre). If $ p, q \in \mathbb{Z} $ with $ q > 0 $ and

$$ \left|\alpha – \frac{p}{q}\right| < \frac{1}{2q^2}, $$

then $ p/q $ is a convergent in the CF expansion of $ \alpha $.

Example. Is $ 22/7 $ a convergent of $ \pi $? We have $ |\pi – 22/7| \approx 0.00127 $ and $ 1/(2 \cdot 49) \approx 0.0102 $. Since $ 0.00127 < 0.0102 $, Legendre’s criterion tells us $ 22/7 $ must be a convergent of $ \pi $. Indeed, $ \pi = [3; 7, 15, 1, \ldots] $ and $ 22/7 = [3; 7] = p_1/q_1 $.

The Matrix Viewpoint

Each convergent computation can be viewed as a matrix product. The matrix

$$ M_n = \begin{pmatrix} a_n & 1 \\ 1 & 0 \end{pmatrix} $$

represents the $ n $th step of the CF algorithm, and

$$ \begin{pmatrix} p_n & p_{n-1} \\ q_n & q_{n-1} \end{pmatrix} = \begin{pmatrix} a_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_1 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} a_n & 1 \\ 1 & 0 \end{pmatrix}. $$

The fundamental identity follows instantly: $ \det M_k = -1 $ for each $ k $, so

$$ \det \begin{pmatrix} p_n & p_{n-1} \\ q_n & q_{n-1} \end{pmatrix} = (-1)^{n+1}, $$

giving $ p_n q_{n-1} – p_{n-1} q_n = (-1)^{n+1} $. These matrices belong to $ GL(2, \mathbb{Z}) $, and the associated Mobius transformations generate the action of the modular group $ PSL(2, \mathbb{Z}) $ on the upper half-plane, connecting continued fractions to hyperbolic geometry and modular forms.

Exercises

Compute the continued fraction expansion of $ 355/113 $ using the Euclidean algorithm.
Find the first 6 convergents of $ \sqrt{5} = [2; \overline{4}] $ and verify they oscillate around $ \sqrt{5} \approx 2.2360679\ldots $
Prove that for the golden ratio $ \varphi = [1; \overline{1}] $, the convergents are ratios of consecutive Fibonacci numbers: $ p_n/q_n = F_{n+2}/F_{n+1} $.
Using Legendre’s criterion, determine whether $ 355/113 $ is a convergent of $ \pi $.
Compute the continued fraction of $ \sqrt{7} $ and verify it has the form $ [2; \overline{1, 1, 1, 4}] $ with palindromic period.
The matrix identity says $ \begin{pmatrix} p_n & p_{n-1} \\ q_n & q_{n-1} \end{pmatrix} = M_0 M_1 \cdots M_n $. Use this to compute the convergents of $ [1; 2, 3] $ by matrix multiplication.
Show that $ \sqrt{2} + 1 = [\overline{2}] $, i.e., it has a purely periodic continued fraction. What does this tell you about the conjugate of $ \sqrt{2}+1 $?