GCD
El MCD (máximo común divisor) es el mayor entero positivo que divide a dos o más enteros, calculado eficientemente con el algoritmo de Euclides.
Propósito
Encontrar el mayor factor común de enteros, usado en la reducción de fracciones y en teoría de números.
Mecanismo
Algoritmo de Euclides: gcd(a,b) = gcd(b, a mod b), hasta b=0. El algoritmo extendido de Euclides encuentra además los coeficientes de Bézout x,y con ax+by=gcd(a,b), usados para inversos modulares. lcm(a,b) = |a×b|/gcd(a,b).
Casos de uso
- Reducción de fracciones
- Cálculo de inversos modulares
- Validación de claves RSA
- Aritmética racional
Ejemplos
- entrada
gcd(48, 18)Output648=6×8, 18=6×3
Errores comunes
- gcd with 0 left unhandled
- gcd(a,0)=|a|, gcd(0,0)=0
Términos relacionados
LCM
El MCM (mínimo común múltiplo) es el menor entero positivo que es múltiplo de dos o más enteros, calculado mediante el MCD. GLOSARIO
Modular Arithmetic
La aritmética modular toma restos tras operaciones enteras, manteniendo los resultados en [0, n); es el fundamento de la teoría de números y la criptografía. GLOSARIO
Prime Number
Un número primo es un número natural mayor que 1 divisible solo entre 1 y sí mismo; es el bloque constituyente de la teoría de números, y todo entero se factoriza de forma única en primos. GLOSARIO