Sliter med en modulus oppgave

[ikky]

Hei!

Har et stykke som jeg ikke får til å regne ut:
151^-1 MOD 2320 = 2151

Noen som kan vise hvordan man kommer fram til 2151?

[Gustav]

[tex]151^{-1} \equiv s \,mod(2320) \Rightarrow 1 \equiv 151s \, mod(2320)\,\! [/tex]

Man må derfor finne et heltallspar [tex](s,t)[/tex] som løser

[tex]1=151s +2320t[/tex]

ved hjelp av Euklids algoritme:

[tex]2320=15*151+55\,\![/tex]
[tex]151=2*55+41\,\![/tex]
[tex]55=41+14\,\![/tex]
[tex]41=2*14+13\,\![/tex]
[tex]14=13+1\,\![/tex]

så

[tex]1=14-13= \cdots=151*(-169)+2320*11\,\![/tex].

Dermed er

[tex]151^{-1} \equiv-169 \equiv (-169+2320) \equiv 2151\, mod(2320) \,\![/tex].