Algoritmo de Euclides

Generalización

En realidad, el algoritmo de Euclides funciona no sólo para los números naturales, sino para cualquier elemento en el que exista una "división con residuo". A este tipo de divisiones se les llama divisiones euclidianas y a los conjuntos donde se puede definir dicha división se les llama dominios euclídeos. Por ejemplo, el conjunto de los números enteros y el de los polinomios con coeficientes racionales son dominios euclídeos porque podemos definir una división con residuo (véase División polinomial). De esta manera, se puede calcular el máximo común divisor de dos números enteros o de dos polinomios.

Por ejemplo, para calcular el máximo común divisor de los polinomios ${\displaystyle P(x)=x^5+2x^3+x}$ y ${\displaystyle Q(x)=x^4-1}$ el algoritmo de Euclides sugiere la siguiente secuencia de operaciones:

De esta manera se concluye que su máximo común divisor es ${\displaystyle -x^2-1}$.

Descripción formal

Se puede expresar este algoritmo de manera más formal usando pseudocódigo. En este caso la expresión "${\displaystyle xmody}$" significa "el residuo de dividir ${\displaystyle x}$ entre ${\displaystyle y}$" (véase Aritmética modular).

Vale la pena notar que este algoritmo no es eficiente ser implementado directamente en una computadora, ya que requeriría memorizar todos los valores de ${\displaystyle r_i}$.

Fundamentos

Existen varias maneras de explicar el algoritmo de Euclides extendido, una de las más comunes consiste en la siguiente:

1. Usar el algoritmo tradicional de Euclides. En cada paso, en lugar de "${\displaystyle a}$ dividido entre ${\displaystyle b}$ es ${\displaystyle q}$ y de resto ${\displaystyle r}$" se escribe la ecuación ${\displaystyle a=bq+r}$ (véase algoritmo de la división).
2. Se despeja el resto de cada ecuación.
3. Se sustituye el resto de la última ecuación en la penúltima, y la penúltima en la antepenúltima y así sucesivamente hasta llegar a la primera ecuación, y en todo paso se expresa cada resto como combinación lineal.

Sin embargo, en aras de la comprensión y memorización de este algoritmo, es conveniente conocer la siguiente caracterización. Para multiplicar dos matrices de tamaño ${\displaystyle 2\times 2}$ se usa la siguiente fórmula (véase Producto de matrices):

(1) [ e f g h ] × [ a b c d ] = [ e a + f c e b + f d g a + h c g b + h d ]

Supóngase que se utiliza el algoritmo de Euclides tradicional para calcular los valores ${\displaystyle q_i}$ y ${\displaystyle r_i}$ que ahí se describen. Por cada valor ${\displaystyle q_i}$ calculado se puede formar la matriz . Usando la ecuación (1) de manera repetida se puede calcular el producto de las primeras ${\displaystyle i}$ matrices de este tipo:

[ s i t i s i + 1 t i + 1 ] = [ 0 1 1 − q i ] × [ 0 1 1 − q i − 1 ] × ⋯ × [ 0 1 1 − q 1 ]

Resulta ser que los valores ${\displaystyle s_i}$ y ${\displaystyle t_i}$ tienen la propiedad de que ${\displaystyle r_i=a{s}_i+b{t}_i}$, es decir, expresan a ${\displaystyle r_i}$ como una combinación lineal de ${\displaystyle a}$ y ${\displaystyle b}$. Particularmente, como ${\displaystyle \mathrm{m}\mathrm{c}\mathrm{d}(a,b)=r_{n+1}}$ entonces se tiene ${\displaystyle \mathrm{m}\mathrm{c}\mathrm{d}(a,b)=a{s}_{n+1}+b{t}_{n+1}}$, lo cual es la solución del problema. Esta propiedad no debería ser sorprendente, pues esta multiplicación de matrices equivale al método antes descrito donde se substituye cada ecuación en la anterior. Es importante calcular ${\displaystyle Q_i\times \cdots \times Q_3\times Q_2\times Q_1}$ en ese mismo orden. La matriz ${\displaystyle Q_1}$ aparece en el extremo derecho y la matriz ${\displaystyle Q_i}$ en el izquierdo.

Regresando al primer ejemplo, la sucesión de cocientes es ${\displaystyle q_1=8}$, ${\displaystyle q_2=1}$ y ${\displaystyle q_3=2}$. Entonces se puede calcular

[ − 1 9 3 − 26 ] = [ 0 1 1 − 2 ] × [ 0 1 1 − 1 ] × [ 0 1 1 − 8 ]

Utilizando el primer renglón de esta matriz se puede leer que ${\displaystyle 91=2366(-1)+273(9)}$, es decir, se ha encontrado la manera de expresar al máximo común divisor de 2366 y 273 como una combinación lineal.

Descripción formal

Para expresar el algoritmo de Euclides extendido es conveniente notar la manera en que se calculan los valores ${\displaystyle s_i}$ y ${\displaystyle t_i}$ con la multiplicación de matrices:

[ s i t i s i + 1 t i + 1 ] = [ s i t i s i − 1 − q i s i t i − 1 − q i t i ] = [ 0 1 1 − q i ] × [ s i − 1 t i − 1 s i t i ]

De esta manera ${\displaystyle s_{i+1}=s_{i-1}-q_i{s}_i}$ y además ${\displaystyle t_{i+1}=t_{i-1}-q_i{t}_i}$. Por lo tanto el algoritmo en pseudocódigo se puede expresar como sigue:

Simplificar fracciones

Al momento de hacer cálculos con fracciones, es de gran importancia saber cómo simplificarlas. Por ejemplo, la fracción ${\displaystyle \frac{65}{91}}$ es equivalente con ${\displaystyle \frac{5}{7}}$ (véase Número racional). De manera más general, ${\displaystyle \frac{a}{b}=\frac{ca}{cb}}$ siempre que ${\displaystyle c\ne 0}$. Para reducir una fracción cualquiera ${\displaystyle \frac{a}{b}}$, sólo se necesita dividir ${\displaystyle a}$ y ${\displaystyle b}$ entre su máximo común divisor.

Por ejemplo, si se desea reducir ${\displaystyle \frac{166}{249}}$, primero se usa el algoritmo de Euclides para encontrar ${\displaystyle \mathrm{m}\mathrm{c}\mathrm{d}(166,249)=83}$. Se hacen las divisiones ${\displaystyle 166÷83=2}$ y ${\displaystyle 249÷83=3}$. Luego entonces se concluye que ${\displaystyle \frac{166}{249}=\frac{2}{3}}$.

Fracciones continuas

La sucesión de divisiones que se efectúan al seguir el algoritmo de Euclides puede ser utilizada para expresar una fracción cualquiera ${\displaystyle \frac{a}{b}}$ como fracción continua. Esto se debe a que si ${\displaystyle a=bq+r}$ y ${\displaystyle r\ne 0}$, entonces

(3) a b = q + 1 b r

Por ejemplo, para encontrar el máximo común divisor de ${\displaystyle 93164}$ y ${\displaystyle 5826}$ el algoritmo genera la siguiente secuencia de divisiones:

Todas estas ecuaciones las podemos hacer parecidas a la ecuación (3 3):

1. ${\displaystyle \frac{93164}{5826}=15+\frac{1}{\frac{5826}{5774}}}$
2. ${\displaystyle \frac{5826}{5774}=1+\frac{1}{\frac{5774}{52}}}$
3. ${\displaystyle \frac{5774}{52}=111+\frac{1}{\frac{52}{2}}}$
4. ${\displaystyle \frac{52}{2}=26}$

Si se sustituye la segunda ecuación en la primera, se obtiene

93164 5826 = 15 + 1 1 + 1 5774 52

Si se repite este proceso de substitución entonces se obtiene la expresión deseada:

93164 5826 = 15 + 1 1 + 1 111 + 1 26

De manera más general, la fracción continua encontrada con este algoritmo siempre es de la forma

a b = q 1 + 1 q 2 + 1 q 3 + 1 ⋱ q n − 1 + 1 q n

Inversos módulo m

Se dice que dos números enteros son congruentes módulo ${\displaystyle m}$ (aunque también se puede generalizar para cualquier otro dominio euclídeo) si al dividirlos entre ${\displaystyle m}$ obtenemos el mismo residuo (véase Congruencia). Por ejemplo, 7 es congruente con 12 módulo 5 porque al dividir 7 entre 5 y 12 entre 5, en ambos casos obtenemos el mismo residuo (que es 2). Cuando ${\displaystyle a}$ es congruente con ${\displaystyle b}$ módulo ${\displaystyle m}$ se escribe ${\displaystyle a\equiv b(\mathrm{mod}m)}$, en el ejemplo anterior se tiene ${\displaystyle 7\equiv 12(\mathrm{mod}5)}$. Supóngase que se conocen los valores de ${\displaystyle a}$, ${\displaystyle b}$ y ${\displaystyle m}$, pero que se desconoce el valor ${\displaystyle x}$ en la siguiente congruencia:

(2) a x ≡ b ( mod m )

Basta encontrar un valor ${\displaystyle a^{-1}}$ que satisfaga: ${\displaystyle a^{-1}a\equiv 1(\mathrm{mod}m)}$, pues de esta manera al multiplicar la ecuación (2) por ${\displaystyle a^{-1}}$ se tendrá la solución deseada:

x ≡ a − 1 b ( mod m )

Al elemento ${\displaystyle a^{-1}}$ se le llama "inverso módulo ${\displaystyle m}$" de ${\displaystyle a}$. Desafortunadamente este valor no siempre existe. Por ejemplo, con ${\displaystyle a=4}$ y ${\displaystyle m=6}$ no existe ningún número entero ${\displaystyle a^{-1}}$ tal que ${\displaystyle a^{-1}4\equiv 1(\mathrm{mod}6)}$. De hecho este valor existe si y sólo si ${\displaystyle \mathrm{m}\mathrm{c}\mathrm{d}(a,m)=1}$ (la existencia de soluciones depende de la condición ${\displaystyle \mathrm{m}\mathrm{c}\mathrm{d}(a,m)|b}$, mientras que la unicidad depende de que el ${\displaystyle \mathrm{m}\mathrm{c}\mathrm{d}(a,m)=1}$). Más aún, si al usar el algoritmo de Euclides extendido (ahora con ${\displaystyle b=m}$) se obtiene ${\displaystyle 1=as+mt}$, entonces el valor ${\displaystyle s}$ es el inverso módulo ${\displaystyle m}$ de ${\displaystyle a}$. Por ejemplo, se desea resolver la ecuación

5 x ≡ 2 ( mod 9 )

Entonces con el algoritmo de Euclides extendido se obtiene que ${\displaystyle \mathrm{m}\mathrm{c}\mathrm{d}(5,9)=1=5(2)+9(-1)}$. Como ${\displaystyle \mathrm{m}\mathrm{c}\mathrm{d}(5,9)=1}$ entonces 5 tiene un inverso módulo ${\displaystyle 9}$. Más aún, como ${\displaystyle 1=5(2)+9(-1)}$, entonces ese inverso es 2. Entonces

x ≡ 2 ( 2 ) ( mod 9 )

Es decir que el valor de ${\displaystyle x}$ es ${\displaystyle 4}$.