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)
|
 |
(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 ![[zeta(2)]^(-1)=6/pi^2](/images/equations/GreatestCommonDivisor/Inline93.svg)
, 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)
|
