Continued Fractions and Diophantine Approximation — The Theory of Rational Approximation

We define finite and infinite continued fractions, prove convergence, and rigorously establish the properties of convergents. We develop the theory of best rational approximations, solve the Pell equation x^2 - Dy^2 = 1 via continued fractions, and discuss the Stern--Brocot tree.

Folio Official

March 1, 2026

1 Definition of Continued Fractions

Definition 1 (Finite continued fraction).

For

a_{0} \in Z

and

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

, the expression

[a_{0}; a_{1}, a_{2}, \dots, a_{n}] = a_{0} + \frac{1}{a _{1} + \frac{1}{a _{2} + \frac{1}{⋱ + \frac{1}{a _{n}}}}}

is called a finite continued fraction. The

a_{i}

are called the partial quotients.

Theorem 2.

Every rational number can be expressed as a finite continued fraction, and the computation corresponds to the Euclidean algorithm.

Proof.

Given

r = p / q

with

q > 0

, the division algorithm gives

p = a_{0} q + r_{1}

with

0 \leq r_{1} < q

. If

r_{1} = 0

, then

r = a_{0}

. If

r_{1} > 0

, then

r = a_{0} + r_{1} / q = a_{0} + 1/ (q / r_{1})

, and we repeat the process with

q / r_{1}

. Since the Euclidean algorithm terminates in finitely many steps, so does this procedure, yielding a finite continued fraction. □

2 Convergents

Definition 3 (Convergent).

The

k

-th convergent of

[a_{0}; a_{1}, \dots, a_{n}, \dots]

C_{k} = p_{k} / q_{k} = [a_{0}; a_{1}, \dots, a_{k}]

, where

p_{k}

and

q_{k}

are defined by the recurrence

p_{k} = a_{k} p_{k - 1} + p_{k - 2}, q_{k} = a_{k} q_{k - 1} + q_{k - 2}

with initial values

p_{- 1} = 1

p_{- 2} = 0

q_{- 1} = 0

q_{- 2} = 1

Theorem 4 (Fundamental properties of convergents).

$p_{k} q_{k - 1} - p_{k - 1} q_{k} = (- 1)^{k - 1}$ for all $k \geq 0$ .
$g cd (p_{k}, q_{k}) = 1$ .
$C_{0} < C_{2} < C_{4} < \dots < α < \dots < C_{5} < C_{3} < C_{1}$ , where $α$ is the value of the infinite continued fraction.

Proof.

(1) By induction on

k

. For

k = 0

p_{0} q_{- 1} - p_{- 1} q_{0} = a_{0} \cdot 0 - 1 \cdot 1 = - 1 = (- 1)^{- 1}

. Inductive step:

p_{k} q_{k - 1} - p_{k - 1} q_{k} = (a_{k} p_{k - 1} + p_{k - 2}) q_{k - 1} - p_{k - 1} (a_{k} q_{k - 1} + q_{k - 2}) = - (p_{k - 1} q_{k - 2} - p_{k - 2} q_{k - 1}) = - (- 1)^{k - 2} = (- 1)^{k - 1}

(2) From (1),

p_{k} q_{k - 1} - p_{k - 1} q_{k} = \pm 1

, so

g cd (p_{k}, q_{k}) ∣ 1

(3) Since

C_{k} - C_{k - 1} = (p_{k} q_{k - 1} - p_{k - 1} q_{k}) / (q_{k} q_{k - 1}) = (- 1)^{k - 1} / (q_{k} q_{k - 1})

, even-indexed convergents increase and odd-indexed ones decrease. One also verifies that

C_{k} - C_{k - 2} = (- 1)^{k - 1} a_{k} / (q_{k} q_{k - 2})

, confirming that the even subsequence is strictly increasing and the odd subsequence is strictly decreasing. □

3 Convergence of Infinite Continued Fractions

Theorem 5.

For

a_{0} \in Z

and

a_{i} \in Z_{> 0}

(

i \geq 1

), the limit

lim_{k \to \infty} C_{k}

exists.

Proof.

Since

q_{k} \geq q_{k - 1} + q_{k - 2}

, the sequence

(q_{k})

is strictly increasing with

q_{k} \to \infty

. Thus

∣ C_{k} - C_{k - 1} ∣ = 1/ (q_{k} q_{k - 1}) \to 0

. By the monotone convergence theorem, the even and odd subsequences each converge, and since the gap between consecutive convergents tends to zero, both limits must coincide. □

4 Best Rational Approximation

Theorem 6.

The convergent

p_{k} / q_{k}

provides the best rational approximation in the following sense: for any rational number

p / q

with

1 \leq q \leq q_{k}

and

p / q \neq = p_{k} / q_{k}

, we have

∣ q_{k} α - p_{k} ∣ < ∣ q α - p ∣

Proof.

Let

p / q \neq = p_{k} / q_{k}

with

1 \leq q \leq q_{k}

. We express

p / q

as an integer linear combination of

p_{k} / q_{k}

and

p_{k - 1} / q_{k - 1}

. Since

p_{k} q_{k - 1} - p_{k - 1} q_{k} = (- 1)^{k - 1}

, the matrix

(q_{k} p_{k} q_{k - 1} p_{k - 1})

has determinant

\pm 1

, so there exist integers

s, t

with

q = s q_{k} + t q_{k - 1}

and

p = s p_{k} + t p_{k - 1}

Since

p / q \neq = p_{k} / q_{k}

, we have

t \neq = 0

. The constraints

q \leq q_{k}

and

q_{k - 1} \geq 1

restrict

s

and

t

(for instance, if

s = 0

, then

q = t q_{k - 1} \leq q_{k}

with

t \geq 1

Now

q α - p = s (q_{k} α - p_{k}) + t (q_{k - 1} α - p_{k - 1})

. By property (3) of convergents, the terms

q_{k} α - p_{k}

and

q_{k - 1} α - p_{k - 1}

have opposite signs. The condition

q \geq 1

forces

s (q_{k} α - p_{k})

and

t (q_{k - 1} α - p_{k - 1})

to have the same sign (or one to vanish), so

∣ q α - p ∣ = ∣ s ∣ \cdot ∣ q_{k} α - p_{k} ∣ + ∣ t ∣ \cdot ∣ q_{k - 1} α - p_{k - 1} ∣ \geq ∣ q_{k - 1} α - p_{k - 1} ∣ > ∣ q_{k} α - p_{k} ∣.

The last inequality follows from the precise estimate

∣ q_{k} α - p_{k} ∣ = ∣ C_{k} - α ∣ \cdot q_{k} < 1/ q_{k + 1} \leq 1/ q_{k}

combined with

∣ C_{k - 1} - α ∣ > ∣ C_{k} - α ∣

and

q_{k - 1} < q_{k}

. □

Remark 7.

This theorem expresses the deep fact that the convergents of a continued fraction provide the best rational approximations to a real number, subject to a constraint on the size of the denominator.

5 The Pell Equation

Theorem 8.

Let

D

be a positive integer that is not a perfect square. The Pell equation

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

has infinitely many positive integer solutions. The smallest solution

(x_{1}, y_{1})

is obtained from the convergents of the continued fraction expansion of

D

, and every solution is given by

(x_{n}, y_{n})

where

x_{n} + y_{n} D = (x_{1} + y_{1} D)^{n}

Proof.

The continued fraction expansion

D = [a_{0}; \overline{a_{1}, \dots, a_{r}}]

is periodic. The convergent

p_{r - 1} / q_{r - 1}

at the end of the first period satisfies

p_{r - 1}^{2} - D q_{r - 1}^{2} = (- 1)^{r}

. If

r

is even,

(p_{r - 1}, q_{r - 1})

is the smallest solution; if

r

is odd,

(p_{2 r - 1}, q_{2 r - 1})

is the smallest solution. That all solutions arise as powers of

(x_{1} + y_{1} D)

follows from the multiplicativity of the norm map on

Z [D]

. □

Example 9.

Consider

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

. Since

2 = [1; \overline{2}]

, the convergents are

C_{0} = 1/1

C_{1} = 3/2

. Checking:

3^{2} - 2 \cdot 2^{2} = 1

, so the smallest solution is

(3, 2)

. The next solution:

(3 + 22)^{2} = 17 + 122

, giving

(17, 12)

Number Theory Algebra Textbook Continued Fractions Pell Equation

Folio Official

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

1 フォロワー·105 記事

Continued Fractions and Diophantine Approximation — The Theory of Rational Approximation

1 Definition of Continued Fractions

2 Convergents

3 Convergence of Infinite Continued Fractions

4 Best Rational Approximation

5 The Pell Equation

あなたの専門知識を世界に発信しよう

Folio Officialの他の記事

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry