Division and Remainders

The Euclidean algorithm is one of the oldest and most important algorithms in mathematics. It computes the greatest common divisor of two integers using repeated division.

Given integers $a$ and $b$ with

the division algorithm states that there exist unique integers $q$ and $r$ such that



The Euclidean algorithm repeatedly applies this decomposition.

For example, to compute

we divide successively:

The last nonzero remainder is

so

Why the Algorithm Works

Suppose

Any common divisor of $a$ and $b$ also divides

Conversely, any common divisor of $b$ and $r$ divides

Thus

The Euclidean algorithm repeatedly replaces a larger pair by a smaller equivalent pair until the remainder becomes zero.

This process must terminate because the remainders form a strictly decreasing sequence of nonnegative integers.

Continued Fractions

The Euclidean algorithm naturally produces continued fractions.

Suppose

Applying repeated division gives

and so forth.

Dividing each equation appropriately yields

$$ \frac{a}{b}

q_0+\frac{1}{q_1+\frac{1}{q_2+\cdots}}. $$

Thus the Euclidean algorithm encodes rational numbers as continued fractions.

For example,

$$ \frac{252}{105}

2+\frac{42}{105}

2+\frac{1}{2+\frac12}. $$

Hence

$$ \frac{252}{105}

[2;2,2]. $$

This connection is fundamental in Diophantine approximation.

Bézout Coefficients

The Euclidean algorithm also produces integers $x,y$ satisfying

This is Bézout identity.

For example, from

and

we obtain

Substituting

gives

$$ 21

105-2(252-105\cdot2). $$

Thus

Hence

The extended Euclidean algorithm systematically computes such coefficients.

Geometric Interpretation

The Euclidean algorithm may be visualized geometrically.

Suppose we begin with a rectangle of side lengths $a$ and $b$, where

One repeatedly removes the largest possible squares of side length $b$. The remaining rectangle has dimensions $b\times r$, where

The process then repeats on the smaller rectangle.

For example, a $252\times105$ rectangle contains two $105\times105$ squares, leaving a $105\times42$ rectangle.

This geometric interpretation explains why continued fractions arise naturally from repeated subdivision.

Complexity and Efficiency

The Euclidean algorithm is extremely efficient.

At each step, the remainders decrease rapidly. In fact, the number of steps required grows only logarithmically with the size of the inputs.

The worst-case behavior occurs when consecutive remainders are Fibonacci numbers.

For example,

requires exactly $n$ divisions.

Thus the Fibonacci sequence measures the slowest possible decrease in the Euclidean algorithm.

Euclidean Domains

The algorithm extends beyond ordinary integers.

In a Euclidean domain, division with remainder is possible. Examples include:

• the integers $\mathbb{Z}$,
• polynomial rings $F[x]$ over fields,
• Gaussian integers $\mathbb{Z}[i]$.

In each case, one obtains:

• greatest common divisors,
• Bézout identities,
• unique factorization properties.

Thus the Euclidean algorithm becomes a structural principle in algebra.

Connection with Rational Approximation

The convergents produced by continued fractions provide excellent rational approximations.

For example,

Its convergents are

These fractions approximate $\sqrt2$ extraordinarily well.

The Euclidean algorithm therefore links arithmetic with approximation theory and irrational numbers.

Historical Perspective

The Euclidean algorithm appears in entity[“book”,“Elements”,“mathematical treatise by Euclid”] and remains one of the oldest algorithms still in active use.

Its influence extends across mathematics:

• elementary number theory,
• continued fractions,
• algebraic structures,
• computational mathematics,
• cryptography,
• computer algebra systems.

The algorithm illustrates a recurring theme in mathematics: repeated local simplification can reveal deep global structure.