MDC por fatores primos

Listar os fatores fica lento para números maiores, e as fatorações em primos são mais rápidas. Fatore os dois números: 45 é $3\cdot 3\cdot 5$ e 75 é $3\cdot 5\cdot 5$. Os primos que eles têm em comum são um 3 e um 5.

Multiplique os primos em comum: $3\cdot 5$ é 15, o MDC de 45 e 75. Um primo só é considerado comum tantas vezes quantas aparece em ambos os números: 45 tem dois 3s, mas 75 tem apenas um, então só um 3 entra.

Por que funciona: um fator comum só pode ser formado pelos primos que ambos os números contêm. Pegando cada primo compartilhado tantas vezes quanto ambos permitem, formamos o maior deles. Com expoentes, pegue cada primo compartilhado com seu menor expoente: ${3}^{2}\cdot 5$ e $3\cdot {5}^{2}$ resultam em $3\cdot 5$.