Greatest common divisor

In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers $x$ , $y$ , the greatest common divisor of $x$ and $y$ is denoted $\gcd(x,y)$ . For example, the GCD of 8 and 12 is 4, that is, $gcd(8, 12) = 4$ .^[1]^[2]

In the name "greatest common divisor", the adjective "greatest" may be replaced by "highest", and the word "divisor" may be replaced by "factor", so that other names include highest common factor, etc.^[3]^[4]^[5]^[6] Historically, other names for the same concept have included greatest common measure.^[7]

This notion can be extended to polynomials (see Polynomial greatest common divisor) and other commutative rings (see § In commutative rings below).

Overview[edit]

Definition[edit]

The greatest common divisor (GCD) of integers $a$ and $b$ , at least one of which is nonzero, is the greatest positive integer $d$ such that $d$ is a divisor of both $a$ and $b$ ; that is, there are integers $e$ and $f$ such that $a = de$ and $b = df$ , and $d$ is the largest such integer. The GCD of $a$ and $b$ is generally denoted $gcd(a, b)$ .^[8]

When one of $a$ and $b$ is zero, the GCD is the absolute value of the nonzero integer: $gcd(a, 0) = gcd(0, a) = | a |$ . This case is important as the terminating step of the Euclidean algorithm.

The above definition is unsuitable for defining $gcd(0, 0)$ , since there is no greatest integer $n$ such that $0 \times n = 0$ . However, zero is its own greatest divisor if greatest is understood in the context of the divisibility relation, so $gcd(0, 0)$ is commonly defined as $0$ . This preserves the usual identities for GCD, and in particular Bézout's identity, namely that $gcd(a, b)$ generates the same ideal as ${a, b}$ .^[9]^[10]^[11] This convention is followed by many computer algebra systems.^[12] Nonetheless, some authors leave $gcd(0, 0)$ undefined.^[13]

The GCD of $a$ and $b$ is their greatest positive common divisor in the preorder relation of divisibility. This means that the common divisors of $a$ and $b$ are exactly the divisors of their GCD. This is commonly proved by using either Euclid's lemma, the fundamental theorem of arithmetic, or the Euclidean algorithm. This is the meaning of "greatest" that is used for the generalizations of the concept of GCD.

Example[edit]

The number 54 can be expressed as a product of two integers in several different ways:

Calculation[edit]

Using prime factorizations[edit]

Greatest common divisors can be computed by determining the prime factorizations of the two numbers and comparing factors. For example, to compute $gcd(48, 180)$ , we find the prime factorizations 48 = 2⁴ · 3¹ and 180 = 2² · 3² · 5¹; the GCD is then 2^min(4,2) · 3^min(1,2) · 5^min(0,1) = 2² · 3¹ · 5⁰ = 12 The corresponding LCM is then 2^max(4,2) · 3^max(1,2) · 5^max(0,1) = 2⁴ · 3² · 5¹ = 720.

In practice, this method is only feasible for small numbers, as computing prime factorizations takes too long.

For positive integers $a$ , $gcd(a, a) = a$ .

Every common divisor of $a$ and $b$ is a divisor of $gcd(a, b)$ .

$gcd(a, b)$ , 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 \cdot p + b \cdot q$ , where p and q are integers. This expression is called . Numbers p and q like this can be computed with the extended Euclidean algorithm.

Bézout's identity

$gcd(a, 0) = | a |$ , for $a \neq 0$ , since any number is a divisor of 0, and the greatest divisor of a is $| a |$ .^[5] This is usually used as the base case in the Euclidean algorithm.

[2]

If a divides the product b⋅c, and $gcd(a, b) = d$ , then a/d divides c.

If m is a positive integer, then $gcd(m \cdot a, m \cdot b) = m \cdotgcd(a, b)$ .

If m is any integer, then $gcd(a + m \cdot b, b) = gcd(a, b)$ . Equivalently, $gcd(a mod b, b) = gcd(a, b)$ .

If m is a positive common divisor of a and b, then $gcd(a / m, b / m) = gcd(a, b)/ m$ .

The GCD is a function: $gcd(a, b) = gcd(b, a)$ .

commutative

The GCD is an function: $gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)$ . Thus $gcd(a, b, c, ...)$ can be used to denote the GCD of multiple arguments.

associative

The GCD is a in the following sense: if a₁ and a₂ are relatively prime, then $gcd(a 1 \cdot a 2, b) = gcd(a 1, b)\cdotgcd(a 2, b)$ .

multiplicative function

$gcd(a, b)$ is closely related to the $lcm(a, b)$ : we have
$gcd(a, b)\cdotlcm(a, b) = | a \cdot b |$ .