Euclid’s algorithm


Euclid’s algorithmMathworldPlanetmath describes a procedure for finding the greatest common divisorMathworldPlanetmath of two integers.

Suppose a,b, and without loss of generality, b>0, because if b<0, then gcd(a,b)=gcd(a,|b|), and if b=0, then gcd(a,b)=|a|. Put d:=gcd(a,b).

By the division algorithm for integers, we may find integers q and r such that a=q0b+r0 where 0r0<b.

Notice that gcd(a,b)=gcd(b,r0), because da and db, so dr0=a-q0b and if b and r0 had a common divisorMathworldPlanetmathPlanetmath d larger than d, then d would also be a common divisor of a and b, contradicting d’s maximality. Thus, d=gcd(b,r0).

So we may repeat the division, this time with b and r0. Proceeding recursively, we obtain

a = q0b+r0 with 0r0<b
b = q1r0+r1 with 0r1<r0
r0 = q2r1+r2 with 0r2<r1
r1 = q3r2+r3 with 0r3<r2

Thus we obtain a decreasing sequence of nonnegative integers b>r0>r1>r2>, which must eventuallyMathworldPlanetmath reach zero, that is to say, rn=0 for some n, and the algorithm terminates. We may easily generalize the previous argument to show that d=gcd(rk-1,rk)=gcd(rk,rk+1) for k=0,1,2,, where r-1=b. Therefore,

d=gcd(rn-1,rn)=gcd(rn-1,0)=rn-1.

More colloquially, the greatest common divisor is the last nonzero remainder in the algorithm.

The algorithm provides a bit more than this. It also yields a way to express the d as a linear combinationMathworldPlanetmath of a and b, a fact obscurely known as Bezout’s lemma. For we have that

a-q0b = r0
b-q1r0 = r1
r0-q2r1 = r2
r1-q3r2 = r3
rn-3-qn-1rn-2 = rn-1
rn-2 = qnrn-1

so substituting each remainder rk into the next equation we obtain

b-q1(a-q0b)=k1a+l1b=r1(a-q0b)-q2(k1a+l1b)=k2a+l2b=r2(k1a+l1b)-q3(k2a+l2b)=k3a+l3b=r3(kn-3a+ln-3b)-qn(kn-2a+ln-2b)=kn-1a+ln-1b=rn-1

Sometimes, especially for manual computations, it is preferable to write all the algorithm in a tabular format. As an example, let us apply the algorithm to a=756 and b=595. The following table details the procedure. The variables at the top of each column (without subscripts) have the same meaning as above. That is to say, r is used for the sequenceMathworldPlanetmath of remainders and q for the corresponding sequence of quotients. The entries in the k and l columns are obtained by multiplying the current values for k and l by the q in this row, and subtracting the results from the k and l in the previous row.

rqkl7561059510116131-11121-344924-5143-11147237-470

Thus, gcd(756,595)=7 and 37756-47595=7.

Euclid’s algorithm was first described in his classic work Elements (see propositionsPlanetmathPlanetmath VII 1 and VII 2), which also contained procedures for geometrical constructions. These are the first known formally described algorithms. Prior to this, informally defined algorithms were in common use to perform various computations, but Elements contained the first attempt to rigorously describe a procedure and explain why its results are admissibleMathworldPlanetmath. Euclid’s algorithm for greatest common divisor is still commonly used today; since Elements was published in the fourth century BC, this algorithm has been in use for nearly 2400 years!

Title Euclid’s algorithm
Canonical name EuclidsAlgorithm
Date of creation 2013-03-22 12:00:04
Last modified on 2013-03-22 12:00:04
Owner rmilson (146)
Last modified by rmilson (146)
Numerical id 21
Author rmilson (146)
Entry type Algorithm
Classification msc 11A05
Synonym Euclidean algorithmMathworldPlanetmath
Related topic BezoutsLemma
Related topic EuclideanRing