Greatest common divisor

In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more non-zero 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.

Overview

Example

The number 54 can be expressed as a product of two other integers in several different ways:

Thus the divisors of 54 are:

Similarly the divisors of 24 are:

The numbers that these two lists share in common are the common divisors of 54 and 24:

The greatest of these is 6. That is the greatest common divisor of 54 and 24. One writes:

Reducing fractions

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 relatively prime, orcoprime

if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.

A geometric view

For example, a 24-by-60 rectangular area can be divided into a grid of: 1-by-1 squares, 2-by-2 squares, 3-by-3 squares, 4-by-4 squares, 6-by-6 squares or 12-by-12 squares. Therefore, 12 is the greatest common divisor of 24 and 60. A 24-by-60 rectangular area can be divided into a grid of 12-by-12 squares, with two squares along one edge (24/12 = 2) and five squares along the other (60/12 = 5).

A 24-by-60 rectangle is covered with ten 12-by-12 square tiles, where 12 is the GCD of 24 and 60. More generally, an a-by-brectangle can be covered with square tiles of side-length c only ifc is a common divisor of a and b.

Calculation

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² 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 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:

48 = 2 × 2 × 2 × 2 × 3,

180 = 2 × 2 × 3 × 3 × 5.

What they share in common is two "2"s and a "3":

Least common multiple = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720

Greatest common divisor = 2 × 2 × 3 = 12.

http://www.khanacademy.org/video/greatest-common-divisor?playlist=Arithmetic