# Euclidean Algorithm Revisited

## 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

$$
a>b>0,
$$

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

$$
a=bq+r,
\qquad
0\le r<b.
$$

$$
a=bq+r
$$

The Euclidean algorithm repeatedly applies this decomposition.

For example, to compute

$$
\gcd(252,105),
$$

we divide successively:

$$
252=105\cdot2+42,
$$

$$
105=42\cdot2+21,
$$

$$
42=21\cdot2+0.
$$

The last nonzero remainder is

$$
21,
$$

so

$$
\gcd(252,105)=21.
$$

## Why the Algorithm Works

Suppose

$$
a=bq+r.
$$

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

$$
a-bq=r.
$$

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

$$
bq+r=a.
$$

Thus

$$
\gcd(a,b)=\gcd(b,r).
$$

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

$$
\frac{a}{b}>1.
$$

Applying repeated division gives

$$
a=bq_0+r_1,
$$

$$
b=r_1q_1+r_2,
$$

$$
r_1=r_2q_2+r_3,
$$

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

$$
ax+by=\gcd(a,b).
$$

This is Bézout identity.

For example, from

$$
252=105\cdot2+42,
$$

and

$$
105=42\cdot2+21,
$$

we obtain

$$
21=105-42\cdot2.
$$

Substituting

$$
42=252-105\cdot2,
$$

gives

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

Thus

$$
21=-2\cdot252+5\cdot105.
$$

Hence

$$
x=-2,
\qquad
y=5.
$$

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

$$
a>b.
$$

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

$$
a=bq+r.
$$

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,

$$
\gcd(F_{n+1},F_n)
$$

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,

$$
\sqrt2=[1;2,2,2,\dots].
$$

Its convergents are

$$
1,\frac32,\frac75,\frac{17}{12},\dots
$$

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.