Euclidean algorithm

This article page is a stub, please help by expanding it.

The Euclidean algorithm (also called Euclid's algorithm) is an efficient method for computing the greatest common divisor (GCD), also known as the greatest common factor (GCF) or highest common factor (HCF). It is named after the Greek mathematician Euclid, who described it in Books VII and X of his Elements.

Algorithmic efficiency

Number of steps

Number of steps in the Euclidean algorithm for

gcd (x, y)

. Red points indicate relatively few steps (quick), whereas yellow, green and blue points indicate successively more steps (slow). The largest blue area follows the line

y = ϕ x

, where

ϕ

represents the Golden ratio.

The number of steps to calculate the GCD of two natural numbers,

a

and

b

, may be denoted by

T (a, b)

. If

g

is the GCD of

a

and

b

, then

a = m g

and

b = n g

for two coprime numbers

m

and

n

. Then

$\begin{array}{l}T(a,b)=T(m,n),a=mg,b=ng,(a,b)=g,(m,n)=1,\end{array}$

as may be seen by dividing all the steps in the Euclidean algorithm by

g

. By the same argument, the number of steps remains the same if

a

and

b

are multiplied by a common factor

w

$\begin{array}{l}T(a,b)=T(wa,wb).\end{array}$

Therefore, the number of steps

T

may vary dramatically between neighboring pairs of numbers, such as

T (a, b)

and

T (a, b + 1)

, depending on the size of the two GCDs.

The recursive nature of the Euclidean algorithm gives another equation

$\begin{array}{l}T(a,b)=1+T(b,r_0)=2+T(r_0,r_1)=\dots =N+T(r_{N-2},r_{N-1})=N+1,\end{array}$

where

T (x, 0) = 0

by assumption.

Worst case number of steps

If the Euclidean algorithm requires

N

steps for a pair of natural numbers

a   >   b   >   0

, the smallest values of

a

and

b

for which this is true are the Fibonacci numbers

FN  + 2

and

FN  + 1

, respectively. This can be shown by induction. If

N = 1

,

b

divides

a

with no remainder; the smallest natural numbers for which this is true is

b = 1

and

a = 2

, which are

F2

and

F3

, respectively. Now assume that the result holds for all values of

N

up to

M  −  1

. The first step of the

M

-step algorithm is

$\begin{array}{l}a=q_{0}b+r_0,\end{array}$

and the second step is

$\begin{array}{l}b=q_1{r}_0+r_1.\end{array}$

Since the algorithm is recursive, it required

M  −  1

steps to find

gcd (b, r0)

and their smallest values are

FM  + 1

and

FM

. The smallest value of

a

is therefore when

q0 = 1

, which gives

a = b + r0 = FM  + 1 + FM = FM  + 2

. This proof, published by Gabriel Lamé in 1844, represents the beginning of computational complexity theory, and also the first practical application of the Fibonacci numbers. This result suffices to show that the number of steps in Euclid's algorithm can never be more than five times the number of its digits (base 10). For if the algorithm requires

N

steps, then

b

is greater than or equal to

FN + 1

which in turn is greater than or equal to

ϕ N  − 1

, where

ϕ

is the golden ratio. Since

b   ≥   ϕ N  − 1

, then

N  −  1   ≤   logϕ b

. Since

log10 ϕ   >   1 5 , N  −  1 5   <   log10 ϕ logϕ b = log10 b.

Thus,

N   ≤   5 log10 b

. Thus, the Euclidean algorithm always needs less than

O (h)

divisions, where

h

is the number of digits in the smaller number

b

.

Applications

Factorization algorithms

Calculating a greatest common divisor is an essential step in several integer factorization algorithms, such as Pollard's rho algorithm, Shor's algorithm, Dixon's factorization method and the Lenstra elliptic curve factorization. The Euclidean algorithm may be used to find this GCD efficiently. Continued fraction factorization uses continued fractions, which are determined using Euclid's algorithm.

Domains

The Euclidean algorithm can be adapted to some other domains. Those domains in which the Euclidean algorithm can be adapted and implemented are then called Euclidean domains.