Algoritmo euclidiano extendido

El algoritmo euclidiano extendido es un algoritmo para calcular enteros xxx e yyy tales que

ax+by=gcd(a,b)ax + by = \gcd(a,b)ax+by=gcd(a,b)

dados aaa y bbb.

La existencia de tales enteros está garantizada por el lema de Bézout.

El algoritmo euclidiano extendido puede verse como el recíproco de la exponenciación modular.

Invirtiendo los pasos del algoritmo euclidiano, es posible encontrar estos enteros xxx e yyy. La idea es empezar con el GCD y trabajar recursivamente hacia atrás. Esto se puede hacer tratando los números como variables hasta que terminemos con una expresión que sea una combinación lineal de nuestros números iniciales. Vamos a hacer esto con el ejemplo que utilizamos anteriormente.

Empezamos con nuestro GCD. Lo reescribimos en términos de los dos términos anteriores:

2=26-2×12.2 = 26 – 2 \times 12 .2=26-2×12.

Sustituimos por 121212 tomando nuestra línea anterior (38=1×26+12)(38 = 1 \times 26 + 12)(38=1×26+12) y escribiéndolo en términos de 12:

2=26-2×(38-1×26).2 = 26 – 2 \times (38 – 1\times 26). 2=26-2×(38-1×26).

Recoge los términos iguales, los 2626, y tenemos

2=3×26-2×38.2 = 3 veces 26 – 2 veces 38. 2=3×26-2×38.

Repite el proceso:

2=3×(102-2×38)-2×38.2 = 3 \times (102 – 2\times 38) – 2\times 38.2=3×(102-2×38)-2×38.

El resultado final es nuestra respuesta:

2=3×102-8×38.2 = 3 \times 102 – 8 \times 38.2=3×102-8×38.

Por tanto, xxx e yyy son 333 y -8-8-8.

Encuentra dos enteros aaa y bbb tales que 1914a+899b=gcd(1914,899).1914a + 899b = \gcd(1914,899). 1914a+899b=gcd(1914,899).

Primero usa el algoritmo de Euclides para encontrar el GCD:

1914=2×899+116899=7×116+87116=1×87+2987=3×29+0.\begin{aligned}1914 &= 2\times 899 + 116 \899 &= 7 \times 116 + 87 \116 &= 1 \times 87 + 29 \87 &= 3 \times 29 + 0.\nd{aligned}191489911687=2×899+116=7×116+87=1×87+29=3×29+0.

De aquí, el último resto no nulo (GCD) es 292929.Ahora usamos el algoritmo extendido:

29=116+(-1)×8787=899+(-7)×116.

Comienza{alineado} 29 &= 116 + (-1)|tiempo 87\87 &= 899 + (-7)|tiempo 116.

Finaliza{alineado}2987=116+(-1)×87=899+(-7)×116.

Sustituyendo por 878787 en la primera ecuación, tenemos

29=116+(-1)×(899+(-7)×116)=(-1)×899+8×116=(-1)×899+8×(1914+(-2)×899)=8×1914+(-17)×899=8×1914-17×899.\Inicio29&= 116 + (-1)veces (899 + (-7)veces 116) \&= (-1)\times 899 + 8\times 116 \&= (-1)\times 899 + 8\times ( 1914 + (-2)\times 899 )\&= 8\times 1914 + (-17) \times 899 \&= 8\times 1914 – 17 \times 899.\end{aligned}29=116+(−1)×(899+(−7)×116)=(−1)×899+8×116=(−1)×899+8×(1914+(−2)×899)=8×1914+(−17)×899=8×1914−17×899.

Como ahora escribimos el GCD como una combinación lineal de dos enteros, terminamos el algoritmo y concluimos

a=8,b=-17. □ a = 8, b =-17. \N – A=8,b=-17. □