Divisibilidad y factorización · Definición

Algoritmo de Euclides extendido

teoría de números elementaldivisibilidad y factorización

Antes de empezar necesitas conocer

Las divisiones sucesivas del algoritmo de Euclides dejan el máximo común divisor como combinación lineal de los números originales. Si se acompañan los coeficientes en cada paso, esa combinación se obtiene sin buscarla a ciegas.

Definición

El algoritmo de Euclides extendido calcula \(d=\operatorname{mcd}(a,b)\) y enteros \(x\), \(y\) tales que \(ax+by=d\). Es el algoritmo de Euclides que además registra los coeficientes de Bézout.

\[r_k=r_{k-2}-q_{k-1}r_{k-1}\\s_k=s_{k-2}-q_{k-1}s_{k-1}\\t_k=t_{k-2}-q_{k-1}t_{k-1}\]

Sean \(r_{-1}=a\) y \(r_0=b\), con \(s_{-1}=1\), \(t_{-1}=0\), \(s_0=0\), \(t_0=1\). En cada paso se divide \(r_{k-2}=q_{k-1}r_{k-1}+r_k\) y se actualizan los coeficientes con la regla de la fórmula, de modo que \(r_k=a\,s_k+b\,t_k\) se mantiene siempre. Cuando el resto se anula, el último resto no nulo es \(d\) y sus coeficientes son los buscados; la identidad de Bézout queda garantizada por esta invariante.

Para \(a=240\) y \(b=46\): \(240=5\cdot 46+10\), \(46=4\cdot 10+6\), \(10=1\cdot 6+4\), \(6=1\cdot 4+2\), \(4=2\cdot 2\). Así \(d=2\). Retrocediendo, \(2=6-4=6-(10-6)=2\cdot 6-10=2(46-4\cdot 10)-10=2\cdot 46-9\cdot 10=2\cdot 46-9(240-5\cdot 46)=47\cdot 46-9\cdot 240\), luego \(x=-9\) e \(y=47\) verifican \(240(-9)+46(47)=2\). Con la tabla de coeficientes se obtiene el mismo resultado sin sustituciones.

Un error típico es olvidar que los coeficientes iniciales son \(s_{-1}=1\), \(t_{-1}=0\) y \(s_0=0\), \(t_0=1\), y comenzar con \(s_0=1\) o \(t_0=1\) para ambos. Esto produce una combinación que no coincide con \(a\) y \(b\). Conviene comprobar siempre que \(ax+by=d\) con los valores finales.

Para pensar

¿Por qué \(x\) e \(y\) no son únicos?

Porque \((x+kb/d,\ y-ka/d)\) también cumple \(ax+by=d\) para todo entero \(k\).

Ejercicios 10

  1. ¿Qué garantiza el algoritmo de Euclides extendido al terminar?
  2. ¿Cuál es el valor inicial de \(s_{-1}\) y \(t_{-1}\) al comenzar?
  3. Si \(\operatorname{mcd}(a,b)=d\), ¿qué relación cumplen \(a\), \(b\) y \(d\) en la identidad de Bézout?
  4. En el paso \(46=4\cdot 10+6\) de la división \(r_{k-2}=q_{k-1}r_{k-1}+r_k\), ¿qué valor tiene \(q_{k-1}\)?
  5. ¿Cuál es el mcd de 240 y 46 según el algoritmo?
  6. Para \(a=30\) y \(b=12\), con \(6=30-2\cdot 12\), ¿qué valor de \(y\) cumple \(30x+12y=6\) con \(x=1\)?
  7. Con \(a=35\) y \(b=15\), el algoritmo da \(\gcd=5\). ¿Cuál es un par válido \((x,y)\) con \(35x+15y=5\)?
  8. Para \(a=17\) y \(b=5\), ¿cuál es el coeficiente \(y\) de la identidad \(17x+5y=1\)?
  9. Si el algoritmo extendido da \(s_k\) y \(t_k\) con \(r_k=as_k+bt_k\), ¿qué debe cumplirse al final del proceso?
  10. Para \(a=99\) y \(b=78\), con \(\operatorname{mcd}(a,b)=3\), ¿qué par \((x,y)\) cumple \(99x+78y=3\)?

Referencias

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 2
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 1