hitta inversen

Hej

jag har lite problem med följande uppgift och skulle behöva lite hjälp:

Finn den multiplikativa inversen till 57 mod 101

Svaret ska bli 39

Jag tänkte använda mig av divisions algoritmen och fick

$101 = 1 * 57 + 44 57 = 1 * 44 + 13 44 = 3 * 13 + 5 13 = 2 * 5 + 3 5 = 1 * 3 + 2 3 = 1 * 2 + 1$

men jag förstår inte var dom får 39 ifrån

Om x är den multiplikativa inversen till 57 mod 101 ska det alltså gälla att

$57x \equiv 1 \pmod{101}$

vilket innebär att det finns ett heltal $y$ sådant att

$57x = 101y + 1$ (definition)

vilket är ekvivalent med

$57x - 101y = 1$

Detta är en linjär diofantisk ekvation och man finner x genom att lösa ekvationen. y är inte viktig men kommer att återfinnas parallellt med att finna x.

Det vanligaste sättet att lösa diofantiska ekvationer av detta slag är via divisionsalgoritmen men då ska man också utföra återsubsitutionsstegen för att finna

$57\times 39 - 101\times 22 = 1$

Svara