3^-1 mod 4 Patr: Witam, nie mog znalezc nigdzie info jak to obliczyc: 3⁻¹ mod 4 Wynik to 3 jak do tego dojsc?

Patr: Albo: 7⁻¹ mod 13? Wynik 2 jak to obliczyc?

jc: Kro stosuje taki zapis? Rozumiem 3⁻¹ w pierścieniu Z₄. Wtedy to faktycznie 3 bo 3*3 mod 4 = 1.

Patr: Niestety tak mam w zadaniu i musze to zrozumieć

jc: Dla danego a masz znaleźć b takie, że ab daje resztę jeden z dzielenia przez n. Dla małych n możesz odgadnąć wynik lub sprawdzać kolejne elementy. Dla większych stosujesz algorytm Euklidesa. 5⁻¹ w Z₇ to 3 bo 5*3=2*7+1. 5⁻¹ w Z₃₇. 37 = 7*5 + 2 5 = 2*2+1 stąd 1=5−2*2=5−2(37−7*5)=15*7 − 2*37 Wynik = 15.

jc: O notację spytałem, bo żadnym podręczniku nie widziałem takiego zapisu.

Patr: Czy moglbym prosic o przykladowe rozwiazanie? Np. 7⁻¹ mod 13

jc: Przecież napisałem 7*2=13+1, dlatego 7⁻¹=2 w Z₁₃. Jeszcze raz spytam, czy widziałeś w jakim podręczniku taką notację? Bo właściwie to 7⁻¹ mod 13 = 7⁻¹, a nie 2.

Patr: Juz prawie rozumiem, tylko skad w: stąd 1=5−2*2=5−2(37−7*5)=15*7 − 2*37 Wzielo sie 15*7?