Euclidean Algorithm

The Problem of Computing GCDs

The greatest common divisor of two integers can be found by listing divisors, but this method becomes inefficient for large numbers. For example, finding

\gcd(1071,462)

by listing all divisors would be tedious.

The Euclidean algorithm gives a fast and systematic method. It reduces a gcd problem to smaller gcd problems by repeated division with remainder.

Basic Principle

The key identity is

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

where

a=bq+r

and

0\le r<b.

This works because the common divisors of $a$ and $b$ are exactly the common divisors of $b$ and $r$ .

Indeed, since

r=a-bq,

any integer dividing both $a$ and $b$ also divides $r$ . Conversely, since

a=bq+r,

any integer dividing both $b$ and $r$ also divides $a$ .

Thus the gcd is unchanged when $(a,b)$ is replaced by $(b,r)$ .

The Algorithm

Let $a$ and $b$ be positive integers with $a\ge b$ .

Apply the division algorithm:

a=bq_1+r_1,\qquad 0\le r_1<b.

If $r_1=0$ , then

\gcd(a,b)=b.

If $r_1\ne0$ , divide $b$ by $r_1$ :

b=r_1q_2+r_2,\qquad 0\le r_2<r_1.

Continue:

r_1=r_2q_3+r_3,

and so on.

The remainders strictly decrease:

b>r_1>r_2>r_3>\cdots\ge0.

Since there is no infinite strictly decreasing sequence of nonnegative integers, the process must stop. The last nonzero remainder is the greatest common divisor.

Example

Compute

\gcd(1071,462).

First divide $1071$ by $462$ :

1071=462\cdot2+147.

Then divide $462$ by $147$ :

462=147\cdot3+21.

Then divide $147$ by $21$ :

147=21\cdot7+0.

The last nonzero remainder is $21$ . Therefore

\gcd(1071,462)=21.

Why the Algorithm Terminates

At each nonzero step, the new remainder is smaller than the previous divisor. Thus the sequence of positive remainders is strictly decreasing.

A strictly decreasing sequence of positive integers cannot continue forever. Eventually a zero remainder must occur.

This termination argument depends on the well-ordering principle for the natural numbers.

GCD Preservation

The essential step is the equality

\gcd(a,b)=\gcd(b,a-bq).

Since the remainder is

r=a-bq,

this gives

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

This identity is often more important than the algorithm itself. It shows that one may replace a number by its remainder modulo another number without changing the gcd.

For example,

\gcd(1071,462)=\gcd(462,147)=\gcd(147,21)=21.

Negative Integers

The Euclidean algorithm is usually stated for positive integers, but it applies to arbitrary integers by taking absolute values:

\gcd(a,b)=\gcd(|a|,|b|).

Thus, for example,

\gcd(-1071,462)=\gcd(1071,462)=21.

If one of the integers is zero, then

\gcd(a,0)=|a|

for $a\ne0$ .

Efficiency

The Euclidean algorithm is efficient because each step reduces the size of the numbers. In many cases the numbers shrink very quickly.

For example, instead of testing all divisors of $1071$ and $462$ , the algorithm uses only three divisions.

The worst case occurs when the remainders decrease as slowly as possible. This is closely related to consecutive Fibonacci numbers. Even then, the number of steps grows only logarithmically with the size of the input.

This efficiency is one reason the Euclidean algorithm is one of the oldest and most important algorithms in mathematics.

Role in Number Theory

The Euclidean algorithm is central to elementary number theory. It computes greatest common divisors, proves Bézout identities, solves linear Diophantine equations, finds modular inverses, and supports the Chinese remainder theorem.

Its importance comes from a simple idea: division with remainder reduces arithmetic questions to smaller ones without changing the essential divisibility structure.

The algorithm is therefore both computational and theoretical. It gives a method for calculation and a framework for proof.