Greatest common divisor

In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers , , the greatest common divisor of and is denoted <math>\gcd (x,y)</math>. For example, the GCD of 8 and 12 is 4, that is, .

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 (HCF), etc. Historically, other names for the same concept have included greatest common measure.

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

Overview

Definition

The greatest common divisor (GCD) of integers and , at least one of which is nonzero, is the greatest positive integer such that is a divisor of both and ; that is, there are integers and such that and , and is the largest such integer. The GCD of and is generally denoted .\right)</math> processors (this is superpolynomial).

Properties

For every positive integer , .
Every common divisor of and is a divisor of .
, 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 , 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.
, for , since any number is a divisor of 0, and the greatest divisor of a is . This is usually used as the base case in the Euclidean algorithm.
If a divides the product b⋅c, and , then a/d divides c.
If m is a positive integer, then .
If m is any integer, then . Equivalently, .
If m is a positive common divisor of a and b, then .
If , then .
The GCD is a commutative function: .
The GCD is an associative function: . Thus can be used to denote the GCD of multiple arguments.
The GCD is a multiplicative function in the following sense: if a<sub>1</sub> and a<sub>2</sub> are relatively prime, then .
is closely related to the least common multiple : we have
: .

: 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:
:
: .
If we have the unique prime factorizations of and where and , then the GCD of a and b is
: .
It is sometimes useful to define and 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, can be interpreted as the number of segments between points with integral coordinates on the straight line segment joining the points and .
For non-negative integers and , where and are not both zero, provable by considering the Euclidean algorithm in base n:
: .
An identity involving Euler's totient function:
: <math> \gcd(a,b) = \sum_{k|a \text{ and }k|b} \varphi(k) .</math>
GCD Summatory function (Pillai's arithmetical function):

<math>\sum_{k=1}^n \gcd(k,n)

= \sum_{d|n} d \varphi \left( \frac n d \right)

=n\sum_{d|n}\frac{\varphi(d)}{d}

=n\prod_{p|n}\left(1+\nu_p(n)\left(1-\frac{1}{p}\right)\right)</math> where <math>\nu_p(n)</math> is the -adic valuation.

Probabilities and expected value

In 1972, James E. Nymann showed that integers, chosen independently and uniformly from , are coprime with probability as goes to infinity, where refers to the Riemann zeta function. (See coprime for a derivation.) This result was extended in 1987 to show that the probability that random integers have greatest common divisor is .

Using this information, the expected value of the greatest common divisor function can be seen (informally) to not exist when . In this case the probability that the GCD equals is , so we have

: <math>\mathrm{E}( \mathrm{2} ) = \sum_{d=1}^\infty d (d^{-2}/\zeta(2)) = \frac{1}{\zeta(2)} \sum_{d=1}^\infty \frac{1}{d}.</math>

This last summation is the harmonic series, which diverges. However, when , the expected value is well-defined, and by the above argument, it is

: <math> \mathrm{E}(k) = \sum_{d=1}^\infty d^{1-k} \zeta(k)^{-1} = \frac{\zeta(k-1)}{\zeta(k)}. </math>

For , this is approximately equal to 1.3684. For , it is approximately 1.1106.

In commutative rings

The notion of greatest common divisor can more generally be defined for elements of an arbitrary commutative ring, although in general there need not exist one for every pair of elements.

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

With this definition, two elements and may very well have several greatest common divisors, or none at all. If is an integral domain, then any two GCDs of and must be associate elements, since by definition either one must divide the other. Indeed, if a GCD exists, any one of its associates is a GCD as well.

Existence of a GCD is not assured in arbitrary integral domains. However, if is a unique factorization domain or any other GCD domain, then any two elements have a GCD. If is a Euclidean domain in which euclidean division is given algorithmically (as is the case for instance when where is a field, or when is the ring of Gaussian integers), then greatest common divisors can be computed using a form of the Euclidean algorithm based on the division procedure.

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

: <math>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.</math>

The elements and <math>1 + \sqrt{-3}</math> are two maximal common divisors (that is, any common divisor which is a multiple of is associated to , the same holds for <math>1 + \sqrt{-3}</math>, but they are not associated, so there is no greatest common divisor of and .

Corresponding to the Bézout property we may, in any commutative ring, consider the collection of elements of the form , where and range over the ring. This is the ideal generated by and , and is denoted simply . 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 ; then this is a greatest common divisor of and . But the ideal can be useful even when there is no greatest common divisor of and . (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 , whence the ring-theoretic term.)

Notes

References

External links

gcd(x,y) = y function graph: https://www.desmos.com/calculator/6nizzenog5