Euklides algoritm

jag ska försöka hitta ax+by= 1
genom euklides algoritm

sgd (40,33) = 1

40 = 1 * 33 + 7
33 = 4 * 7 + 5
7 = 1 * 5 + 2
5 = 2 * 2 + 1
2 = 1 * 2

baklänges blir de ju

1 = 5 - 2 * 2
= 5 - 2(7-1*5)
= (33-4*7) - 2(7-1(33-4*7))
= 33 - 4(40-33) -2(7-1(33-4(40-33)))

hur skriver jag om detta efter denna del?
har lite problem när jag väl kommer till den sista delen av en algoritm
å se hur man får ut "x" och "y"

Du måste byta ut 7 mot 40 - 33:
1 = 33 - 4(40-33) -2(7-1(33-4(40-33)))
= 33 - 4(40-33) -2((40-33)-1(33-4(40-33)))

Sedan kan du förenkla och komma ihåg att alltid behålla 40 och 33:
= 33 - 4(40-33) -2((40-33)-1(33-4*40+4*33))
= 33 - 4(40-33) -2((40-33)-(33-4*40+4*33))
= 33 - 4(40-33) -2((40-33)-33+4*40-4*33)
= 33 - 4(40-33) -2(40-33-33+4*40-4*33)
= 33 - 4(40-33) -2(5*40-6*33)
= 33 - 4(40-33) -10*40 + 12*33
= 33 - 4*40 + 4*33 -10*40 + 12*33
= 17*33 - 14*40

Alltså, 1 = 17*33 - 14*40.

Det är inte x och y du får ut, utan x₀ och y₀.

Det betyder att 17 är den multiplikativa inversen till 33 (mod 40) och att -14 är den multiplikativa inversen till 40 (mod 33). Det är ett delsteg i att lösa en diofantisk ekvation.

Ja, man kan säga att det är en partikulärlösning. Sedan finns homogenlösningar som kan adderas till partikulärlösningen för att få andra lösningar.