Hacemos el algoritmo extendido de Euclides para calcular el mcd.
1895 = 1801 + 94
1801 = 19·94 + 15
94 = 6·15 + 4
15 = 3·4 +3
4 = 3+1
3 = 3·1 +0
Y ahora se recorre el camino hacia atrás. Es un poco lioso de explicar consiste en hacer una combinación lineal primero de 4 y 3, después 15 y 4, después 94 y 15, luego 1801 y 94 y finalmente de 1895 y 1801. Es una tentación efectuar multiplicaciones de más, pero solo deben hacerse las precisas para conseguir esas combinaciones lineales que te he dicho
4=3+1 ==> 1=4-3
3=15-3·4 ==> 1 =4 - 15 + 3·4 = 4·4 - 15
4=94-6·15 ==> 1 = 4(94-6·15) -15 = 4·94 - 25·15
15=1801-19·94 ==> 1 = 4·94 - 25(1801-19·94) = 479·94 -25·1801
94=1895-1801 ==> 1 = 479(1895-1801)-25·1801 = 479·1895 - 504·1801
Esa es la combinación lineal
1 = 479·1895 - 504·1801
La comprobamos
1 = 907705 - 907704
Está bien.
Y eso es todo.
