Run time of the Euclidean algorithm
Woden Kusner
University of Pittsburgh
Introduction
The Euclidean algorithm is an ancient technique for quickly computing the
greatest common divisor of two numbers using repeated applications of the
division algorithm. This was described in Euclids Elements (c. 300 BC).
Given a pair of integers a, d, |a| |d|, we may compute the g.c.d.(a, d) by
constructing a sequence of quotients and remainders
a = q 0 d + r0
d = q 1 r 0 + r1
r0 = q 2 r 1 + r2
..
.
..
.
rn2 = qn rn1 + rn
rn1 = qn+1 rn + 0
with rn , the last non-zero remainder, as the g.c.d.(a, d). The Euclidean
algorithm terminates as |b| > |r0 | > |r1 | > ... > |rn | is a strictly decreasing
sequence of positive integers.[1]
In 1844, Gabriel Lame proved one of the first results in computational
complexity theory: the first worst case running time an algorithm.[4] Lames
original result stated
Theorem. The number of steps (divisions) in an application of the Euclidean algorithm never exceeds 5 times the number of digits (base 10) of
the lesser number.
We will examine a more modern statement, but the method of proof
remains similar. The adjustments needed for Lames original result may be
found in Honsburger. [2]
Division Algorithm:
Given integers a, d
with d 6= 0, there
exist unique integers
q,r such that
a = qd + r
and
0 r < |d|
A Theorem of Lam
e
The main theorem of this section is
Theorem. [3] The length of the Euclidean algorithm applied to a, b with
a b is bounded by
ln a
+1
ln
where is the golden ratio.
We will follow with a proof combining methods attributed to Sierpinski
and Grossman[2] and Nathanson[3].
Lemma 1. Given n, let an be the lesser of a pair (an+1 , an ) for which the
Euclidean algorithm requires n steps. Then
Fibonacci Numbers:
F1 := 1
F2 := 1
Fn := Fn1 + Fn2
for n 2
an Fn+1
Proof. Now we may construct a lower bound for an .
0 < an1 < an
an+1 = qn an + an1
a
=
q
a
+
a
0
< an2 < an1
n
n1
n1
n2
a
=
q
a
+
a
0
<
an3 < an2
n2 n2
n3
n1.
..
..
.
n steps
..
..
.
.
a
=
q
a
+
a
0
<
a
3
2 2
1
1 < a2
a2 = q1 a1 + 0
q1 > 1
Notice q1 6= 1. Otherwise a2 = a1 , a contradiction to the Euclidean
algorithm. Therefore q1 2, also, a1 1. For all other q, qi 1, n i > 1.
We have inequalities ak ak1 + ak2 , with a1 1 = F2 and a2 2 = F3 .
Therefore ak Fk + 1 for all k, in particular, an Fn + 1
We will now establish a relationship between and the Fibonacci Numbers.
Lemma 2.
n = Fn + Fn1
Proof. We proceed by induction.
The base case is follows trivially from definitions
a+b
a
= :=
a
b
a = b
b + b
=
b
+ 1 = 2
2 = F2 + F1
We may assume
n1 = Fn1 + Fn2
2
n1 = (Fn1 + Fn2 )
n = Fn1 2 + Fn2
n = Fn1 ( + 1) + Fn2
n = (Fn1 + Fn2 ) + Fn1
n = Fn + Fn1
This lemmas lead directly to
Corollary.
n1 = Fn +
Fn1
Fn + Fn1 = Fn+1
With these established, we may prove our main theorem.
Proof. Lemma 1 and Corollary to Lemma 2 yield the following sequence of
inequalities
an Fn+1 n1
As the values of an and are both strictly greater than 1, and ln is an
increasing function, we have
ln an (n 1) ln
Hence the desired result
n
ln an
+1
ln
References
[1] David S. Dummit and Richard M. Foote. Abstract Algebra. John Wiley
and Sons, Inc, 2004.
[2] Ross Honsberger. Mathematical Gems II: Dolciani Mathematical Expositions 2. MAA, 1976.
[3] Melvyn B. Nathanson. Elementary Methods in Number Theory. Springer,
1999.
[4] Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery. An Introduction to the Theory of Numbers. John Wiley and Sons, Inc, 1991.
