MCD a partir de factores primos

Buscar los factores se vuelve lento con números más grandes, y las descomposiciones en factores primos son más rápidas. Descompón ambos números en factores: 45 es 3 × 3 × 5 y 75 es 3 × 5 × 5. Los factores primos que comparten son un 3 y un 5.

Multiplica los factores primos compartidos: 3 × 5 es 15, el MCD de 45 y 75. Un factor primo cuenta como compartido solo tantas veces como aparece en ambos números: 45 tiene dos 3, pero 75 solo tiene uno, así que se incluye solo un 3.

Por qué funciona: un factor común solo puede formarse a partir de primos que contengan ambos números. Tomar cada primo compartido tantas veces como lo permitan ambos números da como resultado el mayor factor común. Con exponentes, toma cada primo compartido con su exponente menor: 3^2 × 5 y 3 × 5^2 dan 3 × 5.