The greatest common divisor, or GCD, is the largest number that divides two or more integers without a remainder. For 12 and 18, the divisors are 1, 2, 3, 6 for both, so the GCD is 6. The GCD is also called the greatest common factor.

Euclid's algorithm finds the GCD efficiently. Divide the larger by the smaller, then replace the larger with the remainder, and repeat until the remainder is zero. The last nonzero remainder is the GCD. The method is over two thousand years old and still used in computer science.

The GCD simplifies fractions. Dividing numerator and denominator by their GCD reduces a fraction to lowest terms. It also appears in modular arithmetic, cryptography, and number theory. The least common multiple relates to the GCD by the formula LCM(a, b) = a × b / GCD(a, b).

• Largest number dividing integers exactly
• Found by Euclid's algorithm
• Used to simplify fractions
• Relates to LCM by a simple formula