Name
• Prime numbers
• Math
Edit

In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more integers (at least one of which is not zero), 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 Polynomial greatest common divisor, or to rational numbers (with integer quotients).

Overview

Notation

In this article we will denote the greatest common divisor of two integers a and b as gcd(a,b). Some older textbooks use (a,b).[1][2]

Example

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

$54 \times 1 = 27 \times 2 = 18 \times 3 = 9 \times 6. \,$

Thus the divisors of 54 are:

$1, 2, 3, 6, 9, 18, 27, 54. \,$

Similarly the divisors of 24 are:

$1, 2, 3, 4, 6, 8, 12, 24. \,$

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

$1, 2, 3, 6. \,$

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

$\gcd(54,24) = 6. \,$

Reducing fractions

The greatest common divisor is useful for reducing fractions to be in lowest terms. For example, gcd(42, 56) = 14, therefore,

$\frac{42}{56}=\frac{3 \cdot 14 }{ 4 \cdot 14}=\frac{3 }{ 4}.$

Coprime numbers

Two numbers are called relatively prime, or coprime 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).

Using Euclid's algorithm

A much more efficient method is the Euclidean algorithm, which uses a division algorithm such as long division in combination with the observation that the gcd of two numbers also divides their difference. To compute gcd(48,18), 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. Note that we ignored the quotient in each step except to notice when the remainder reached 0, signalling that we had arrived at the answer. Formally the algorithm can be described as:

$\gcd(a,0) = a$
$\gcd(a,b) = \gcd(b, a \,\mathrm{mod}\, b)$,

where

$a \,\mathrm{mod}\, b = a - b \left\lfloor {a \over b} \right\rfloor$.

If the arguments are both greater than zero then the algorithm can be written in more elementary terms as follows:

$\gcd(a,a) = a$
$\gcd(a,b) = \gcd(a - b,b)\quad,$ if a > b
$\gcd(a,b) = \gcd(a, b-a)\quad,$ if b > a

C++