Guía: máximo común divisor (MCD)
What is GCD?
El máximo común divisor (MCD) es el mayor número entero que divide sin resto a dos o más enteros. Por ejemplo, MCD(48, 18) = 6, porque 6 es el mayor número que divide exactamente tanto a 48 como a 18. El MCD es un concepto fundamental de la teoría de números y la criptografía.
Euclidean Algorithm
The oldest and most efficient method for calculating GCD is the Euclidean algorithm. It relies on repeated division: GCD(a, b) = GCD(b, a mod b), until b equals 0. For example: GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) = 6. This algorithm is extremely fast and works even for very large numbers.
Properties of GCD
MCD(a, b) * mcm(a, b) = a * b (el producto del MCD y el mcm es igual al producto de los números). Si MCD(a, b) = 1, entonces a y b son primos entre sí. El MCD es siempre menor o igual que el menor de los dos números. MCD(0, a) = |a| para cualquier número a distinto de cero.
Practical Applications
El MCD sirve para simplificar fracciones: se dividen numerador y denominador entre el MCD para obtener una fracción irreducible. En criptografía RSA se emplea al generar claves de cifrado. En informática determina la mayor división común de recursos de memoria o procesador. En música permite determinar intervalos comunes para los ritmos.