:O rączszka: 7 x = 1 mod 17 Jak to zrobić?

Jack: zerknij tu: https://matematykaszkolna.pl/forum/88545.html

rączszka: Nie wiem, czy o to chodzi? 3=1*17−2*7 1=1*7−2*3 0=1*3−3*1

Jack: NWD(17 i 7)=1 więc rozwijamy aż do reszty równej 1 (następna musi być równa 0). 17=2*7 + 3 ⇒ 3=17−2*7 7=2*3 +1 ⇒ 1=7−2*3 Stąd 1=7−2*3=7−2(17−2*7)=−2*17+5*7=5*7−2*17

rączszka: Dzięki chyba rozumiem

aczkolwiek: ale co tu jest tym elementem odwrotnym? wlasnie to 5*7−2*17

Jack: 5 bo 1= 5*7−2*17 1= 5 * 7 (mod 17) czyli z def. liczby odwrotnej modulo: 5 jest taką liczbą, że 7 *5 =1 (mod 17) (czyli 5 i 7 są wzajemnie odwrotne)