Euclidean algorithm
The Euclidean algorithm (also known as the Euclidean division algorithm or Euclid's algorithm) is an algorithm that finds the greatest common divisor (GCD) of two elements of a Euclidean domain, the most common of which is the nonnegative integers , without factoring them.
Contents
Main idea and informal description
The basic idea is to repeatedly use the fact that
If we have two non-negative integers with
and
, then the greatest common divisor is
. If
, then the set of common divisors of
and
is the same as the set of common divisors of
and
where
is the remainder of division of
by
. Indeed, we have
with some integer
, so, if
divides both
and
, it must divide both
and
and, thereby, their difference
. Similarly, if
divides both
and
, it should divide
as well. Thus, the greatest common divisors of
and
and of
and
coincide:
. But the pair
consists of smaller numbers than the pair
! So, we reduced our task to a simpler one. And we can do this reduction again and again until the smaller number becomes
General Form
Start with any two elements and
of a Euclidean Domain
- If
, then
.
- Otherwise take the remainder when
is divided by
, and find
.
- Repeat this until the remainder is 0.
Then
Usually the Euclidean algorithm is written down just as a chain of divisions with remainder:
for
and so
Simple Example
To see how it works, just take an example. Say . We have
, so
. Similarly,
, so
. Then
, so
. Thus
.
Linear Representation
An added bonus of the Euclidean algorithm is the "linear representation" of the greatest common divisor. This allows us to write , where
are some elements from the same Euclidean Domain as
and
that can be determined using the algorithm. We can work backwards from whichever step is the most convenient.
In the previous example, we can work backwards from equation :