In mathematics, the greatest common divisor (gcd), also known as the greatest common denominator, greatest common factor (gcf), or highest common factor (hcf), of two or more nonzero integers, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.
This notion can be extended to polynomials, see greatest common divisor of two polynomials.
Contents
Overview
The greatest common divisor is useful for reducing fractions to be in lowest terms. For example, gcd(42, 56) = 14, therefore,
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. Two numbers are called coprime or relatively prime if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.
Calculating the gcd
Using prime factorizations
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^{2} and 84 = 2^{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 small numbers; computing prime factorizations in general takes far too long.
Here is another concrete example, illustrated by a Venn diagram. Suppose it is desired to find the greatest common divisor of 48 and 180. First, find the prime factorizations of the two numbers:
What they share in common is two "2"s and a "3":
Using Euclid's algorithm
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 48 by 18 to get a quotient of 2 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. Formally, it can be described as:
Full article ▸
