Greatest common divisor (Euclid’s algorithm)

Greatest common divisor (Euclid’s algorithm)

If d is a divisor of a and d is also a divisor of b, then d is a common divisor of a and b.

The greatest common divisor of two integers a and b, not both zero, is the largest of the common divisors of a and b; denote it by gcd(a, b).

Euclid’s algorithm is described for efficiently computing the greatest common divisor of two integers. Euclid’s algorithm for computing greatest common divisors relies on the following theorem.

Theorem (GCD recursion theorem): For any non negative integer a and any positive integer b, gcd(a, b) = gcd (b, a mod b).

Euclid’s algorithm

The Elements of Euclid (circa 300 B.C.) describes the following gcd algorithm, Euclid’s algorithm is  a recursive program based directly on GCD recursion theorem. The inputs a and b are arbitrary non negative integers. 

Example:

Computation of gcd (30, 21).

EUCLID (30, 21) 

= EUCLID (21, 9)

= EUCLID (9, 3)

= EUCLID (3, 0)

= 3.

The running time of Euclid’s algorithm

The worst-case running time of EUCLID can be analyzed as a function of the size of a and b. Assume that a > b ≥ 0. The overall running time of EUCLID is proportional to the number of recursive calls it makes.

The extended form of Euclid’s algorithm

An important property of common divisors is that d | a and d | b implies d | (a + b) and d | (a – b). 

The notation d | a (read “d divides a”).

More generally, if d | a and d | b implies d | (ax + by) for any integers x and y.

Extend Euclid’s algorithm to compute the integer coefficients x and y such that d = ax + by . or,

gcd(a, b) = ax + by . Note that x and y may be zero or negative.

The procedure EXTENDED-EUCLID takes as input a pair of non negative integers and returns a triple of the form (d, x, y) that satisfies the equation d = ax + by.
Example:

Since the number of recursive calls made in EUCLID is equal to the number of recursive calls made in EXTENDED-EUCLID, the running times of EUCLID and EXTENDED-EUCLID are the same, to within a constant factor. That is, for a > b > 0, the number of recursive calls is O(lg b).