Algoritmo de Euclides

Teoría

El Algoritmo de Euclides es una técnica fundamental en teoría de números que sirve para calcular de forma eficiente el máximo común divisor (MCD) de dos enteros. Aunque en teoría puedes encontrar el MCD sacando la factorización en primos de ambos números, factorizar se vuelve muy difícil cuando los números son muy grandes. El Algoritmo de Euclides se salta este problema usando el algoritmo de la división para reducir el tamaño de los números paso a paso, manteniendo siempre el mismo MCD. El proceso sigue hasta que uno de los números se vuelve cero; en ese momento, el número que no es cero es el MCD.

La intuición detrás del algoritmo se basa en la propiedad de que si un número $d$ divide tanto a $a$ como a $b$, también tiene que dividir a cualquier combinación lineal de ellos, como $a - b$ o $a - kb$. Geométricamente, esto es como decir que si un cuadrado de lado $d$ puede cubrir perfectamente un rectángulo de $a \times b$, también puede cubrir el rectángulo que queda después de quitar tantos cuadrados de $b \times b$ como sea posible. Este paso de reducción te permite cambiar el par $(a, b)$ por el par más pequeño $(b, a \pmod b)$ sin cambiar el conjunto de divisores comunes.

Este algoritmo aparece por todos lados en las matemáticas de competencia, como en el AMC 10/12 y el AIME. Más allá de solo encontrar el MCD, sirve como base para el Algoritmo de Eu