Máximo Común Divisor
El máximo común divisor (MCD) es el número más grande que divide de manera exacta a dos o más números.
Formula
\text{GCF}(a,b) = \text{product of shared prime factors with minimum exponents}
Definition
El máximo común divisor (MCD) de dos o más números es el número más grande que divide a todos ellos de manera exacta, también llamado el mayor factor común. Se puede hallar listando los factores, mediante la factorización prima (tomando el exponente mínimo de cada primo compartido), o mediante el algoritmo de Euclides, $\text{GCF}(a,b) = \text{GCF}(b, a \bmod b)$. Algebraicamente, $\text{GCD}(a,b)$ es el generador del ideal $a\mathbb{Z} + b\mathbb{Z}$ en $\mathbb{Z}$, igual a $\min\{ax + by : x,y \in \mathbb{Z}, ax+by > 0\}$; la identidad de Bézout garantiza que existen enteros $x,y$ tales que $ax + by = \text{GCD}(a,b)$, y el MCD se generaliza a cualquier dominio euclidiano o dominio de ideales principales.
Example
MCD de $12$ y $18$: los factores de $12$ son $1,2,3,4,6,12$, los factores de $18$ son $1,2,3,6,9,18$, y el mayor en común es $6$, útil para simplificar $12/18$ a $2/3$. $\text{GCF}(48, 36)$: $48 = 2^4 \times 3$, $36 = 2^2 \times 3^2$, así que $\text{GCF} = 2^2 \times 3 = 12$, coincidiendo con la cadena euclidiana $\text{GCF}(48,36) = \text{GCF}(36,12) = \text{GCF}(12,0) = 12$. Los coeficientes de Bézout para $\text{GCD}(48,36) = 12$ son $12 = 48(1) + 36(-1)$, hallados mediante el algoritmo de Euclides extendido, esencial para calcular inversos modulares en criptografía.
Key Insight
El MCD es útil para simplificar fracciones. El algoritmo de Euclides es uno de los algoritmos más antiguos conocidos (Euclides, ~300 a.C.) y uno de los más eficientes, ejecutándose en $O(\log(\min(a,b)))$ pasos. En cualquier dominio de ideales principales, el MCD se define mediante el ideal $aR + bR$; para los enteros gaussianos $\mathbb{Z}[i]$, $\text{GCD}(1+i, 3) = 1+i$, ya que $|1+i|^2 = 2$ divide en las factorizaciones de $3$ de manera compatible.