Euclidean algorithm
In mathematics, the Euclidean
algorithm[a] is an efficient
method for computing the
greatest common divisor (GCD).
The algorithm is also called
Euclid’s algorithm, after the
ancient Greek mathematician
Euclid, who first described it.
The GCD of two numbers is
the largest number that divides
both of them without leaving a
remainder. The Euclidean al-
gorithm is based on the prin-
ciple that the greatest common
divisor of two numbers does not
change if the smaller number is
subtracted from the larger num-
ber. For example, 21 is the GCD
of 252 and 105 (252 = 21 × 12,
105 = 21 × 5), which is the
same as the GCD of 147 and
105, since 252 − 105 = 147.
Since the larger number is re-
duced, repeating this process
gives successively smaller num-
bers until one of them is zero.
When that occurs, the GCD is
the remaining nonzero number.
Such a procedure described by
well-defined rules is called an
algorithm. By reversing the
steps, the GCD can be ex-
pressed as a sum of the two ori-
ginal numbers each multiplied
by a positive or negative in-
teger, e.g., 21 = 5 × 105 + (−2)
× 252. This important property
is known as Bézout’s identity.
Euclid’s algorithm was first
described in Euclid’s Elements
(c. 300 BC), making it one of
the oldest numerical algorithms
still in common use. The origin-
al algorithm was described only
for natural numbers and geo-
metric lengths (real numbers),
but the algorithm was general-
ized in the 19th century to oth-
er types of numbers, such as
Animation
Animation
of the
Euclidean
algorithm
for 252
and 105.
The
crossbars
represent
the units
of 21, the
greatest
common
divisor
(GCD). In
each step,
the smal-
ler num-
ber is
subtrac-
ted from
the larger
number,
until one
number is
reduced
to zero.
The re-
maining
number is
the GCD.
Gaussian integers and polyno-
mials of one variable. This led
to modern abstract algebraic
notions such as Euclidean do-
mains. The Euclidean algorithm
has been generalized further to
other mathematical structures,
such as knots and multivariate
polynomial