Pregunta 5 de 5 de Teo de Num

Y esto dice que las técnicas usadas anteriormente pueden servir para calcular el mcd como cambinación lineal de a y m.

Por ejemplo:

Es fácil ver que (519, 1967) = 1

Bueno, no tal fácil creo yo, lo haré con Máxima

519 = 3 · 173

1967 = 7 · 281

Vale es cierto que el mcd es 1

Entonces dice que plantea la ecuación de congruencias

519x :~ 1 (mod 1967)

Ahora aplica el método 3 y multiplica por el entero mas cercano a m/a

1967 / 519 = 3.78.. luego multiplica por 4

2076x :~ 4 (mod 1967)

Reduce el término de la izquierda

2076- 1967 = 109

109x :~ 4 (mod 1967)

Aplica de nuevo el método 3.

1976 / 109 = 18.12 multiplica por 18

1962 :~ 72 (mod 1967)

Reduce el primer término y queda

-5x :~ 72 (mod 1967)

Adicionalmente también resta 1967 a 72 para que quede un múltiplo de 5

-5x :~ -1895 (mod 1967)

Y ahora divide por -5 que es coprimo con 1967 y se mantiene la congruencia

x :~ 379

Como x es la solución de la ecuación planteada que era

519x :~ 1 (mod 1967) tenemos aplicando la definición de números congruentes

519·379 = 1+ 1967s

s = (519·379 - 1)/1967 = 100

luego

519·379 = 1 + 1967·100

1 = 519·379 - 1967·100

Que a mí me gusta más poner

379·519 + 100·1967 = 1

Y lo que hemos hecho es calcular los coeficientes de la combinación lineal

r·519 + s·1967 = (519, 1967) = 1

Que tendríamos que haber usado el algoritmo de euclides ampliado par conseguirlo.

Pues que quieres que te diga, lo hemos conseguido pero con unas ocurrencias que no se le ocurren a cualquiera, mientras que el algoritmo de Euclides te lleva siempre a la respuesta sin tener que tener ninguna iluminación, solo a base de constancia y cálculos.

Y eso es todo.