Definitions

# Greatest common divisor

In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder.

This notion has been extended to polynomials, see Greatest common divisor of two polynomials.

## Overview

The greatest common divisor of a and b is written as gcd(ab), or sometimes simply as (ab). For example, gcd(12, 18) = 6, gcd(−4, 14) = 2 and gcd(5, 0) = 5. Two numbers are called coprime or relatively prime if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.

The greatest common divisor is useful for reducing fractions to be in lowest terms. For example, gcd(42, 56)=14, therefore,

$\left\{42 over 56\right\}=\left\{3 cdot 14 over 4 cdot 14\right\}=\left\{3 over 4\right\}.$

## Calculating the gcd

Greatest common divisors can in principle be computed by determining the prime factorizations of the two numbers and comparing factors, as in the following example: to compute gcd(18,84), we find the prime factorizations 18 = 2·32 and 84 = 22·3·7 and notice that the "overlap" of the two expressions is 2·3; so gcd(18,84) = 6. In practice, this method is only feasible for very small numbers; computing prime factorizations in general takes far too long.

A much more efficient method is the Euclidean algorithm, which uses the division algorithm in combination with the observation that the gcd of two numbers also divides their difference: divide 84 by 18 to get a quotient of 4 and a remainder of 12. Then divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a remainder of 0, which means that 6 is the gcd.

The series of quotients generated by the Euclidean algorithm compose a continued fraction.

If a and b are not both zero, the greatest common divisor of a and b can be computed by using least common multiple (lcm) of a and b:

$operatorname\left\{gcd\right\}\left(a,b\right)=frac\left\{acdot b\right\}\left\{operatorname\left\{lcm\right\}\left(a,b\right)\right\}.$

Keith Slavin has shown that for odd a≥1:

$operatorname\left\{gcd\right\}\left(a,b\right)=log_2prod_\left\{k=0\right\}^\left\{a-1\right\} \left(1+e^\left\{-2ipi k b/a\right\}\right)$

which is a function that can be evaluated for complex b. Marcelo Polezzi has shown that:

$operatorname\left\{gcd\right\}\left(a,b\right)=2sum_\left\{k=1\right\}^\left\{a-1\right\} lfloor k b/arfloor+a+b-a b$

for positive integers a and b. Donald Knuth has proved the following reduction:

$operatorname\left\{gcd\right\}\left(2^a-1,2^b-1\right)=2^\left\{gcd\left(a,b\right)\right\}-1$

for non-negative integers a and b, where a and b are not both zero.

## Properties

• Every common divisor of a and b is a divisor of gcd(ab).
• gcd(ab), where a and b are not both zero, may be defined alternatively and equivalently as the smallest positive integer d which can be written in the form d = a·p + b·q where p and q are integers. This expression is called Bézout's identity. Numbers p and q like this can be computed with the extended Euclidean algorithm.
• gcd(a, 0) = |a|, for a ≠ 0, since any number is a divisor of 0, and the greatest divisor of a is |a|. This is usually used as the base case in the Euclidean algorithm.
• If a divides the product b·c, and gcd(ab) = d, then a/d divides c.
• If m is a non-negative integer, then gcd(m·am·b) = m·gcd(ab).
• If m is any integer, then gcd(a + m·bb) = gcd(ab).
• If m is a nonzero common divisor of a and b, then gcd(a/mb/m) = gcd(ab)/m.
• The gcd is a multiplicative function in the following sense: if a1 and a2 are relatively prime, then gcd(a1·a2b) = gcd(a1b)·gcd(a2b).
• The gcd is a commutative function: gcd(a, b) = gcd(b, a).
• The gcd is an associative function: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c).
• The gcd of three numbers can be computed as gcd(abc) = gcd(gcd(ab), c), or in some different way by applying commutativity and associativity. This can be extended to any number of numbers.
• gcd(ab) is closely related to the least common multiple lcm(ab): we have

gcd(ab)·lcm(ab) = a·b.
This formula is often used to compute least common multiples: one first computes the gcd with Euclid's algorithm and then divides the product of the given numbers by their gcd. The following versions of distributivity hold true:
gcd(a, lcm(bc)) = lcm(gcd(ab), gcd(ac))
lcm(a, gcd(bc)) = gcd(lcm(ab), lcm(ac)).

• It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a complete distributive lattice with gcd as meet and lcm as join operation. This extension of the definition is also compatible with the generalization for commutative rings given below.
• In a Cartesian coordinate system, gcd(ab) can be interpreted as the number of points with integral coordinates on the straight line joining the points (0, 0) and (ab), excluding (0, 0).

## Probabilities and expected value

The probability that two randomly chosen (unlimited) integers $A$ and $B$ have a given greatest common divisor $d$ is $6over \left\{pi^2 d^2\right\}$. This follows from the characterization of $gcd\left(A,B\right)$ as the integer $d$ such that $d|A,B$ and $A/d$ and $B/d$ are coprime. The probability of two integers sharing a factor $d$ is $d^\left\{-2\right\}$. The probability that two integers are coprime is $1/zeta\left(2\right)=6/pi^2$. (See coprime for a derivation.)

Using this information, the expected value of the greatest common divisor function can be computed. This is

$mathrm\left\{E\right\}\left(mathrm\left\{2\right\} \right) = sum_\left\{d=1\right\}^\left\{infty\right\} d frac\left\{6\right\}\left\{pi^2 d^2\right\} = frac\left\{6\right\}\left\{pi^2\right\} sum_\left\{d=1\right\}^\left\{infty\right\} frac\left\{1\right\}\left\{d\right\}.$

This last summation is the Harmonic series, which diverges. Hence the expected value of the greatest common divisor of two variables is not well-defined. This is not the case in general, however. For the greatest common divisor of $k ge 3$ variables, the expected value is well-defined, and by the above argument, it is

$mathrm\left\{E\right\}\left(k\right) = sum_\left\{d=1\right\}^\left\{infty\right\} d^\left\{1-k\right\} zeta\left(k\right)^\left\{-1\right\} = frac\left\{zeta\left(k-1\right)\right\}\left\{zeta\left(k\right)\right\}.$

where $zeta\left(k\right)$ is the Riemann zeta function.

For $k=3$, this is approximately equal to 1.3684. For $k=4$, it is approximately 1.1106.

if all integers x are limited as $m ge x ge 1$ then the results can be extended to

$mathrm\left\{E\right\}\left(k,m\right) = frac\left\{sum_\left\{d=1\right\}^\left\{m\right\} d^\left\{1-k\right\}\right\}\left\{sum_\left\{t=1\right\}^\left\{m\right\} t^\left\{-k\right\}\right\} = frac\left\{zeta\left(k-1\right)-zeta\left(k-1,m+1\right)\right\}\left\{zeta\left(k\right)-zeta\left(k,m+1\right)\right\}.$

where $zeta\left(k,m\right)$ is the Hurwitz zeta function.

if different $m$'s are known for different $x$ then the lowest $m$ is taken.

## The gcd in commutative rings

The greatest common divisor can more generally be defined for elements of an arbitrary commutative ring.

If R is a commutative ring, and a and b are in R, then an element d of R is called a common divisor of a and b if it divides both a and b (that is, if there are elements x and y in R such that d·x = a and d·y = b). If d is a common divisor of a and b, and every common divisor of a and b divides d, then d is called a greatest common divisor of a and b.

Note that with this definition, two elements a and b may very well have several greatest common divisors, or none at all. But if R is an integral domain then any two gcd's of a and b must be associate elements. Also, if R is a unique factorization domain, then any two elements have a gcd. If R is a Euclidean domain then a form of the Euclidean algorithm can be used to compute greatest common divisors.

The following is an example of an integral domain with two elements that do not have a gcd:

$R = mathbb\left\{Z\right\}left\left[sqrt\left\{-3\right\}right\right],quad a = 4 = 2cdot 2 = left\left(1+sqrt\left\{-3\right\}right\right)left\left(1-sqrt\left\{-3\right\}right\right),quad b = left\left(1+sqrt\left\{-3\right\}right\right)cdot 2.$

The elements $1+sqrt\left\{-3\right\}$ and $2$ are two "maximal common divisors" (i.e. any common divisor which is a multiple of 2 is associated to 2, the same holds for $1+sqrt\left\{-3\right\}$), but they are not associated, so there is no greatest common divisor of a and b.

Corresponding to the Bezout property we may, in any commutative ring, consider the collection of elements of the form $p a + q b$, where p and q range over the ring. This is the ideal generated by a and b, and is denoted simply $\left(a,b\right)$. In a ring all of whose ideals are principal (a principal ideal domain or PID), this ideal will be identical with the set of multiples of some ring element d; then this d is a greatest common divisor of a and b. But the ideal $\left(a,b\right)$ can be useful even when there is no greatest common divisor of a and b. (Indeed, Ernst Kummer used this ideal as a replacement for a gcd in his treatment of Fermat's Last Theorem, although he envisioned it as the set of multiples of some hypothetical, or ideal, ring element d, whence the ring-theoretic term.)