# Greatest common divisor

#### Did you know...

SOS Children volunteers helped choose articles and made other curriculum material A good way to help other children is by sponsoring a child

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.

## 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 vulgar fractions to be in lowest terms. For example, gcd(42, 56)=14, therefore,

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

## 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{gcd}(a,b)=\frac{a\cdot b}{\operatorname{lcm}(a,b)}.$

## 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.

## Probabilities and expected value

The probability that two randomly chosen (unlimited) integers $A$ and $B$ have a given greatest common divisor $d$ is $6\over {\pi^2 d^2}$. This follows from the characterization of $gcd(A,B)$ 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^{-2}$. The probability that two integers are coprime is $1/\zeta(2)=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{E}( \mathrm{2} ) = \sum_{d=1}^{\infty} d \frac{6}{\pi^2 d^2} = \frac{6}{\pi^2} \sum_{d=1}^{\infty} \frac{1}{d}.$

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{E}(k) = \sum_{d=1}^{\infty} d^{1-k} \zeta(k)^{-1} = \frac{\zeta(k-1)}{\zeta(k)}.$

where $\zeta(k)$ 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{E}(k,m) = \frac{\sum_{d=1}^{m} d^{1-k}}{\sum_{t=1}^{m} t^{-k}} = \frac{\zeta(k-1)-\zeta(k-1,m+1)}{\zeta(k)-\zeta(k,m+1)}.$

where $\zeta(k,m)$ 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{Z}\left[\sqrt{-3}\right],\quad a = 4 = 2\cdot 2 = \left(1+\sqrt{-3}\right)\left(1-\sqrt{-3}\right),\quad b = \left(1+\sqrt{-3}\right)\cdot 2.$

The elements $1+\sqrt{-3}$ 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{-3}$), 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 $(a,b)$. 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 $(a,b)$ 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.)