All courses › Discrete Mathematics › Greatest common divisor

Greatest common divisor

The greatest common divisor is the largest number that divides two integers. Euclid's algorithm finds it quickly by dividing repeatedly and replacing the numbers with the remainder until the remainder is zero. The last non-zero remainder is the answer.

gcd⁡(a,b)=gcd⁡(b, a mod b)\gcd(a, b) = \gcd(b,\ a \bmod b)Euclid's algorithm
lcm(a,b)=a bgcd⁡(a,b)\text{lcm}(a,b) = \frac{a\,b}{\gcd(a,b)}least common multiple

Symbols

gcd⁡\gcdgreatest common divisor
lcm\text{lcm}least common multiple

Example

gcd⁡(84,36)\gcd(84, 36): 84 mod 36=1284 \bmod 36 = 12 and 36 mod 12=036 \bmod 12 = 0.

The answer is 12.

The algorithm is fast even for large numbers, because the numbers at least halve every other round.
Practise graphs and modular arithmetic for free →

← Modular arithmetic

Part of Discrete Mathematics: Graphs and modular arithmetic.