Greatest common divisor

From Wikipedia, the free encyclopedia

  (Redirected from Highest common factor)
Jump to: navigation, search

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.

Contents

[edit] Overview

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. For example, gcd(42, 56)=14, therefore,

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

[edit] 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)}.

[edit] 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. 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(a, b) = d, then a/d divides c.
  • If m is a non-negative integer, then gcd(m·a, m·b) = m·gcd(a, b).
  • If m is any integer, then 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 a1 and a2 are relatively prime, then gcd(a1·a2, b) = gcd(a1, b)·gcd(a2, b).
  • 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(a, b, c) = gcd(gcd(a, b), c), or in some different way by applying commutativity and associativity. This can be extended to any number of numbers.
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.

[edit] 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 / ζ(2) = 6 / π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 ζ(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 ζ(k,m) is the Hurwitz zeta function.

if different m's are known for different x then the lowest m is taken.

[edit] 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 pa + qb, 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.)

[edit] See also

[edit] References

[edit] External links

Retrieved from "http://en.wikipedia.org/wiki/Greatest_common_divisor"
Personal tools