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 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 vulgar fractions to be in lowest terms. Consider for instance

<math>{42\over56}={3\cdot14\over4\cdot14}={3\over4}<math>

where we cancelled 14, the greatest common divisor of 42 and 56.

Contents

1 Calculating the GCD 2 Properties 3 The gcd in commutative rings 4 External links

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·3² and 84 = 2²·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: 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.

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 the smallest positive integer d which can be written in the form d = a·p + b·q where p and q are integers. Numbers p and q like this can be computed with the extended Euclidean algorithm.

If a divides the product b·c, and gcd(a, b) = d, 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 is a multiplicative function in the following sense: if a₁ and a₂ are relatively prime, then gcd(a₁·a₂, b) = gcd(a₁, b)·gcd(a₂, b).

The gcd of three numbers can be computed as gcd(a, b, c) = gcd(gcd(a, b), c) = gcd(a, gcd(b, c)). Thus the gcd is an associative operation.

gcd(a, b) is closely related to the least common multiple lcm(a, b): we have

gcd(a, b)·lcm(a, b) = 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(b, c)) = lcm(gcd(a, b), gcd(a, c))

lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c)).

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(a, b) can be interpreted as 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 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 don't have a gcd:

<math>R = \mathbb{Z}[\sqrt{-3}],\quad a = 4 = 2\cdot 2 = (1+\sqrt{-3})(1-\sqrt{-3}),\quad b = (1+\sqrt{-3})\cdot 2<math>

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

External links

• Online HCF calculator (http://www.maths.hscripts.com/hcf.php)
• Online gcd calculator (http://wims.unice.fr/wims/wims.cgi?module=tool/popup.en&search=gcd)
• LCM and GCF solvers, work shown (http://www.algebra.com/algebra/homework/Least-Common-Multiple-Greatest-Common-Denominator/Solvers.html) These solvers use algorithm described in wikipedia.de:Größter gemeinsamer Teiler

eo:Plej granda komuna divizoro es:Máximo común divisor fr:Plus grand commun diviseur id:Faktor persekutuan terbesar id:Massimo comun divisore ja:最大公約数 nl:Grootste gemene deler pl:NajwiÄ™kszy wspólny dzielnik ru:Наибольший общий делитель sl:največji skupni delitelj fi:Suurin yhteinen tekijä sv:största gemensamma delare th:ตัวหารร่วมมาก zh:最大公因數