Skip to content

Finite Continued Fractions

A finite continued fraction is an expression of the form

number-theory book chatgpt

From Division to Expansion

A finite continued fraction is an expression of the form

a0+1a1+1a2+⋯+1an, a_0+\frac{1}{a_1+\frac{1}{a_2+\cdots+\frac{1}{a_n}}},

where

a0∈Z a_0\in\mathbb{Z}

and

a1,a2,…,an∈Z>0. a_1,a_2,\ldots,a_n\in\mathbb{Z}_{>0}.

It is usually written compactly as

[a0;a1,a2,…,an]. [a_0;a_1,a_2,\ldots,a_n].

Finite continued fractions are another way to write rational numbers. They arise directly from the Euclidean algorithm.

First Examples

Consider

[2;3]. [2;3].

This means

2+13=73. 2+\frac13=\frac73.

Now consider

[1;2,2]. [1;2,2].

Then

[1;2,2]=1+12+12=1+152=1+25=75. [1;2,2] = 1+\frac{1}{2+\frac12} = 1+\frac{1}{\frac52} = 1+\frac25 = \frac75.

Thus continued fractions express rational numbers by successive reciprocal operations.

Constructing a Continued Fraction

Let

ab \frac{a}{b}

be a positive rational number. Divide aa by bb:

a=bq0+r1,0≤r1<b. a=bq_0+r_1, \qquad 0\le r_1<b.

Then

ab=q0+r1b=q0+1b/r1. \frac{a}{b} = q_0+\frac{r_1}{b} = q_0+\frac{1}{b/r_1}.

Now apply the same process to

br1. \frac{b}{r_1}.

Since the Euclidean algorithm terminates, this process produces a finite continued fraction.

For example,

4319=2+519=2+119/5. \frac{43}{19} = 2+\frac{5}{19} = 2+\frac{1}{19/5}.

Next,

19=5⋅3+4, 19=5\cdot3+4,

so

195=3+45=3+15/4. \frac{19}{5}=3+\frac45 = 3+\frac{1}{5/4}.

Then

5=4⋅1+1, 5=4\cdot1+1,

and

4=1⋅4+0. 4=1\cdot4+0.

Therefore

4319=[2;3,1,4]. \frac{43}{19}=[2;3,1,4].

Convergents

The successive truncations of a continued fraction are called convergents.

For

[a0;a1,a2,…,an], [a_0;a_1,a_2,\ldots,a_n],

the convergents are

[a0], [a_0], [a0;a1], [a_0;a_1], [a0;a1,a2], [a_0;a_1,a_2],

and so on.

For example, the continued fraction

[2;3,1,4] [2;3,1,4]

has convergents

2,[2;3]=73,[2;3,1]=94,[2;3,1,4]=4319. 2,\qquad [2;3]=\frac73,\qquad [2;3,1]=\frac94,\qquad [2;3,1,4]=\frac{43}{19}.

These convergents are rational approximations to the final value.

Recurrence Relations

Convergents can be computed efficiently by recurrence.

Define

p−2=0,p−1=1, p_{-2}=0,\qquad p_{-1}=1, q−2=1,q−1=0. q_{-2}=1,\qquad q_{-1}=0.

For k≥0k\ge0, set

pk=akpk−1+pk−2, p_k=a_kp_{k-1}+p_{k-2}, qk=akqk−1+qk−2. q_k=a_kq_{k-1}+q_{k-2}.

Then the kk-th convergent is

pkqk=[a0;a1,…,ak]. \frac{p_k}{q_k}=[a_0;a_1,\ldots,a_k].

These formulas avoid repeatedly simplifying nested fractions.

Determinant Identity

The convergents satisfy the important identity

pkqk−1−pk−1qk=(−1)k−1. p_kq_{k-1}-p_{k-1}q_k=(-1)^{k-1}.

This implies in particular that

gcd⁡(pk,qk)=1. \gcd(p_k,q_k)=1.

Thus every convergent is already written in lowest terms.

The determinant identity also shows that consecutive convergents are close:

∣pkqk−pk−1qk−1∣=1qkqk−1. \left| \frac{p_k}{q_k} - \frac{p_{k-1}}{q_{k-1}} \right| = \frac{1}{q_kq_{k-1}}.

As denominators grow, consecutive convergents become increasingly close.

Uniqueness

Every positive rational number has a finite continued fraction expansion, but there is a minor ambiguity at the end.

For example,

[2;3]=2+13=73, [2;3]=2+\frac13=\frac73,

while

[2;2,1]=2+12+11=2+13=73. [2;2,1]=2+\frac{1}{2+\frac11} = 2+\frac13 = \frac73.

Thus

[2;3]=[2;2,1]. [2;3]=[2;2,1].

To make the expansion unique, one usually requires the final partial quotient to satisfy

an>1. a_n>1.

Under this convention, every rational number has a unique finite simple continued fraction.

Relation to the Euclidean Algorithm

Finite continued fractions and the Euclidean algorithm contain the same data.

For

ab, \frac{a}{b},

the partial quotients

a0,a1,…,an a_0,a_1,\ldots,a_n

are exactly the quotients that appear in the Euclidean algorithm applied to aa and bb.

Thus continued fractions record the division history of a pair of integers.

This connection explains why continued fractions are so effective in problems involving greatest common divisors, rational approximation, and Diophantine equations.

Arithmetic Meaning

Finite continued fractions give a structured representation of rational numbers. Unlike decimal expansions, they are deeply tied to divisibility.

For example, decimal notation depends on powers of 1010. Continued fractions depend instead on the Euclidean algorithm, and therefore on the intrinsic arithmetic of the numerator and denominator.

This makes continued fractions a natural language for number theory.

Toward Infinite Continued Fractions

Rational numbers give finite continued fractions because the Euclidean algorithm terminates.

Irrational numbers lead to infinite continued fractions. These infinite expansions provide exceptionally good rational approximations and play a central role in the theory of Diophantine approximation.

The finite theory is therefore the gateway to continued fractions for irrational numbers, Pell equations, and quadratic irrationals.