Números primos, MCD y MCM · Lección 5 de 10
El máximo común divisor
Calcular el MCD por factorización y por Euclides.
Antes de empezar, una de repaso
Recordar algo cuesta más que releerlo, y por eso funciona mejor. Esta pregunta es de una lección anterior.
Los factores comunes al menor exponente
Descomponiendo los dos números, el MCD se obtiene tomando los primos que aparecen en ambos, cada uno elevado al menor de sus dos exponentes.
Es intuitivo pero lento: factorizar números grandes es costoso.
El algoritmo de Euclides
Se divide el mayor entre el menor y se guarda el resto. Después se repite con el menor y ese resto, hasta que el resto sea cero. El último divisor no nulo es el MCD.
No necesita factorizar nada y es rapidísimo: con números de cien cifras termina en unos pocos cientos de pasos.
El algoritmo más antiguo en uso
Aparece en los Elementos de Euclides, hacia el 300 a. C., y sigue siendo el mejor método conocido. Muy pocas cosas en tecnología duran veintitrés siglos sin quedarse obsoletas.
Dos números con MCD igual a 1 se llaman coprimos: no comparten ningún factor. Es la condición que hace irreducible una fracción.
Practica
Cada ejercicio se genera con números nuevos y lo corrige el mismo motor que mueve las calculadoras del sitio. La lección se da por dominada al acertar 4 de los últimos 5.
¿Quieres comprobar tus propios números? Esta calculadora resuelve lo mismo paso a paso: Calculadora de MCD.