Máximo Divisor Comum

É o maior número inteiro positivo que divide os dois sem deixar resto. Em português a sigla é MDC; nos textos em inglês ele aparece como GCD, GCF ou HCF, mas o valor é o mesmo. Para 12 e 16 ele é 4.

Fatore os dois números em primos e multiplique aqueles que aparecem nas duas fatorações, tantas vezes quantas estiverem em ambas. 12 = 2 × 2 × 3 e 16 = 2 × 2 × 2 × 2 têm em comum 2 × 2, portanto o MDC é 4.

Euclides o descreveu nos Elementos por volta de 300 a.C.: divide-se o maior número pelo menor e troca-se o par pelo menor número e pelo resto, até que o resto seja 0. Com 16 e 12: 16 dividido por 12 deixa resto 4 e 12 dividido por 4 deixa resto 0, logo o MDC é 4. Nada precisa ser fatorado, e por isso o método continua rápido com números grandes demais para a fatoração.