|
In mathematics, the greatest common divisor (gcd) or
highest common factor (hcf) of two integers which are not both zero
is the largest integer that divides both numbers.
The greatest common divisor of a and b is written as gcd(a, b), or sometimes simply
as (a, b). 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. Consider for instance
-
where we cancelled 14, the greatest common divisor of 42 and 56.
Calculating the gcd
While the gcd of two numbers can in principle be computed by determining the prime factorizations of the two numbers and comparing factors, this is never done in practice, because it is
too slow. A much more efficient method is the Euclidean
algorithm. An extended version of this
algorithm can also compute integers p and q such that
a·p + b·q = gcd(a, b).
Properties
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 follows: it is the smallest positive integer d which can be written in the form
a·p + b·q where p and q are integers.
If gcd(a, b) = d and a divides the product b·c, then
a/d divides c.
If m is any integer, then
gcd(m·a, m·b) = m·gcd(a, b) and
gcd(a + m·b, b) = gcd(a, b). If m is
a nonzero common divisor of a and b, then
gcd(a/m, b/m) = gcd(a, b)/m.
The gcd of three numbers can be computed as gcd(a, b, c) =
gcd(gcd(a, b), c) = gcd(a, gcd(b, c)).
gcd(a, b) is closely related to the least common multiple lcm(a, b): we have
- gcd(a, b)·lcm(a, b) = a·b.
Furthermore, the following versions of distributivity hold true:
-
gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a,
c))
-
lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a,
c)).
Geometrically, gcd(a, b) is the number of points with integral coordinates on the straight line joining
the points (0, 0) and (a, b), excluding (0, 0).
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 of c 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 c·x = a and
c·y = b). If c is a common divisor of a and b, and every common
divisor of a and b divides c, then c is called a greatest common divisor of a and
b.
Note that gcd(a, b) need not be unique, but if R is an integral domain then any two gcd's of a and b must be associate elements. Also, a and b need not have a gcd at all unless R
is a unique factorization domain. If
R is a Euclidean domain then a form of the Euclidean
algorithm can be used to compute the gcd.
External links
|