Máximo Común Divisor (MCD)

Teoría

El máximo común divisor (MCD) de dos enteros es el entero positivo más grande que divide a ambos. También lo puedes encontrar como el factor común más grande; el MCD es fundamental en la teoría de números y tiene aplicaciones en todas las matemáticas.

El algoritmo de Euclides te da un método eficiente para calcular el MCD, basándose en el principio de que $\gcd(a, b) = \gcd(b, a \mod b)$. Este algoritmo es uno de los más antiguos que existen y aparece en los Elementos de Euclides por ahí del año 300 a.C.

Propiedades y aplicaciones clave:

• Dos enteros son primos relativos (o coprimos) si y solo si $\gcd(a, b) = 1$
• Lo usas para simplificar fracciones
• Es esencial para resolver ecuaciones diofánticas lineales
• Es la base de la aritmética modular y de la criptografía RSA

Fórmulas Clave

Definición: $$\gcd(a, b) = \max{d > 0 : d \mid a \text{ and } d \mid b}$$

Algoritmo de Euclides: $$\gcd(a, b) = \gcd(b, a \mod b)$$ $$\gcd(a, 0) = a$$

A partir de la factorización en primos:

Si $a = \prod p_i^{a_i}$ y $b = \prod$