Calculadora de MCD y MCM

El MCD (o MCF — máximo común factor) de dos o más enteros es el mayor entero positivo que los divide a todos sin resto. Ejemplos: MCD(12, 8) = 4; MCD(15, 25) = 5; MCD(7, 13) = 1 (coprimos). El MCD se usa para simplificar fracciones (divida numerador y denominador por el MCD), en el cifrado RSA, para calcular mínimos comunes múltiplos y en aritmética modular.

El MCM de dos o más enteros es el menor entero positivo divisible por todos ellos. Ejemplos: MCM(4, 6) = 12; MCM(3, 7) = 21; MCM(12, 18) = 36. El MCM se usa para encontrar denominadores comunes al sumar fracciones, para programar eventos repetitivos (dos autobuses que llegan cada 15 y 20 minutos se encuentran cada MCM(15, 20) = 60 minutos) y en aritmética modular.

El algoritmo euclidiano (300 a. C.) calcula el MCD de manera eficiente. mcd(a, b) = mcd(b, a mod b), con mcd(a, 0) = a. Ejemplo: mcd(48, 18): 48 = 2×18 + 12; 18 = 1×12 + 6; 12 = 2×6 + 0 → MCD = 6. El algoritmo se ejecuta en tiempo O(log(min(a,b))). El algoritmo binario del MCD (algoritmo de Stein, 1967) usa operaciones a nivel de bit y es más rápido en procesadores sin división por hardware.

Para cualesquiera dos enteros positivos a y b: MCD(a, b) × MCM(a, b) = a × b. Por lo tanto, MCM(a, b) = (a × b) / MCD(a, b). Esto evita calcular el MCM por separado. Para más de dos números, calcule iterativamente: MCD(a, b, c) = MCD(MCD(a, b), c); MCM(a, b, c) = MCM(MCM(a, b), c). Esto se debe a que el MCD y el MCM son operaciones asociativas.

Cuando MCD(a, b) = 1, los números son coprimos (o primos relativos): no comparten factores comunes distintos de 1. Ejemplos: 8 y 9 son coprimos; 15 y 28 son coprimos. En teoría de números, los pares coprimos son fundamentales: la función totiente de Euler, la generación de claves RSA (e y φ(n) deben ser coprimos), los inversos modulares y el Teorema Chino del Resto requieren coprimalidad. La fracción a/b está en su mínima expresión si y solo si MCD(a, b) = 1.