Euclidean algorithm
The Euclidean algorithm allows to find the greatest common divisor of any two non-negative integers. The main idea is very simple: 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
.
To see how it works, just take an example ,
. We have
, so the pair
can be replaced by
. Similarly,
, so we get the pair
. Now,
, so we get the pair
, which has the greatest common divisor
. Thus
.
Usually the Euclidean algorithm is written down just as a chain of divisions with remainder:
The Euclidean algorithm has one nice bonus: the so called linear representation of the greatest common divisor. To see how it works, let's use our equations backwards starting with the last but one:
i.e., is expressed as a sum of
and
with integer coefficients.
How fast is the Euclidean algorithm? One can prove that if the larger of two numbers does not exceed the -th Fibonacci number, then the required number of steps does not exceed
, so the number of steps is logarithmic in the size of the initial numbers (i.e., the number of steps is not much more than the number of digits in the largest of the two numbers).
Practice Problems
- AIME 1985 #13 Let
be the greatest common divisor of
and
for
. What is the maximum value of
?