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.

Related Topics:
Mathematics - Integer - Divides

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

Related Topics:
Vulgar fraction - In lowest terms

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:{42over56}={3cdot14over4cdot14}={3over4}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

~ ~ ~ ~ ~ ~ ~ ~ ~ ~