Greatest Common Divisor

The greatest common divisor, sometimes also called the highest common divisor (Hardy and Wright 1979, p. 20), of two positive integers and is the largest divisor common to and . For example, , , and . The greatest common divisor can also be defined for three or more positive integers as the largest divisor shared by all of them. Two or more positive integers that have greatest common divisor 1 are said to be relatively prime to one another, often simply just referred to as being "relatively prime."

Various notational conventions are summarized in the following table.

notation	source
	this work, Zwillinger (1996, p. 91), Råde and Westergren (2004, p. 54)
	Gellert et al. (1989, p. 25), D'Angelo and West (1990, p. 13), Graham et al. (1990, p. 103), Bressoud and Wagon (2000, p. 7), Yan (2002, p. 30), Bronshtein et al. (2007, pp. 323-324), Wolfram Language
g.c.d.	Andrews 1994, p. 22

The greatest common divisor of , , ... is implemented in the Wolfram Language as GCD[a, b, ...].

The plot above shows with rational . Here, is the greatest rational number for which all the are integers. It is easy to see that if , where , then . Furthermore, if is extended by setting it equal to 0 if is irrational, the resulting function is continuous at the irrationals, discontinuous at the rationals, and has Riemann integral equal to 0 over any finite interval.

The above plots show a number of visualizations of in the -plane. The figure on the left is simply , the figure in the middle is the absolute values of the two-dimensional discrete Fourier transform of (Trott 2004, pp. 25-26), and the figure at right is the absolute value of the transform of .

If is the greatest common divisor of and , then is the largest possible integer satisfying

			(1)
			(2)

with and positive integers.

The Euclidean algorithm can be used to find the greatest common divisor of two integers and to find integers and such that

(3)

The notion can also be generalized to more general rings than simply the integers . However, even for Euclidean rings, the notion of GCD of two elements of a ring is not the same as the GCD of two ideals of a ring. This is sometimes a source of confusion when studying rings other than , such as polynomial rings in several variables.

To compute the GCD, write the prime factorizations of and ,

			(4)
			(5)

where the s are all prime factors of and , and if does not occur in one factorization, then the corresponding exponent is taken as 0. Then the greatest common divisor is given by

(6)

where min denotes the minimum. For example, consider .

			(7)
			(8)

so

(9)

The GCD is distributive

(10)

(11)

and associative

			(12)
			(13)
			(14)

If and , then

			(15)
			(16)

so . The GCD is also idempotent

(17)

commutative

(18)

and satisfies the absorption law

(19)

A recurrence equation that converges to for positive odd and is given by

(20)

with and , where is the greatest dividing exponent of in (Stehlé and Zimmerman 2004). The plot above shows the number of iterations required to converge for odd .

The probability that two integers picked at random are relatively prime is , where is the Riemann zeta function. Polezzi (1997) observed that , where is the number of lattice points in the plane on the straight line connecting the vectors (0, 0) and (excluding itself). This observation is intimately connected with the probability of obtaining relatively prime integers, and also with the geometric interpretation of a reduced fraction as a string through a lattice of points with ends at (1,0) and . The pegs it presses against give alternate convergents of the continued fraction for , while the other convergents are obtained from the pegs it presses against with the initial end at (0, 1).

Knuth showed that

(21)

Wolfram Web Resources