. asdf: Element odwrotny modulo: mam takie zadanie: znaleźć element odwrotny dla 11 mod (20) 11⁻¹ = k : 11*k≡1(mod 20) 11*k + 20 = 1 20 = 1*11 + 9 11 = 1*9 + 2 9 = 4*2 + 1 −−−−−−−−−−−−− 1 = 9−4*2 = 9 − 4*(11−9) = 9 − 4*11 + 4*9 = 5*9 − 4*11 = 5*9 − 4*(20−9) = 5*9 − 4*20+4*9 = 9*9−4*20...ale to mi nic nie da pozniej musze rozwiazac: 11*k + 20 = 9*9 − 4*20 11k = 81 − 5*20 11k = −19 i nic nie da, jak to rozwiązać? (proszę o wskazowke)

asdf: ?

Mila: To w pamięci można ustalic : 11*11=121=1 (mod20) Rozszerzony algorytm Euklidesa 11x=1 (mod20) 20=1*11+9 11=1*9+2 9=4*2+1 2=2*1+0 1=1*9−4*2= =1*9−4*(11−9)= =1*9−4*11+4*9= =−4*11+5*9= =−4*11+5*(20−1*11)= =−4*11+5*20−5*11= =−9*11+5*20⇔ −9 jest elementem odwrotnym do 11 w Z₂₀ możesz przejść na dodatnią liczbę −9+20=11 Jak podałam na początku.

niechciany: 20 = 1*11 + 9 11 = 1*9 + 2 9 = 4*2 + 1 i mamy : 1 = 9 − 4 *2 = 9 − 4*11 + 4*9 = 5*9 − 4*11 = 5*20 − 9 * 11 mamy : 1 = 5 * 20 − 9 * 11 mod 20 1 = −9 * 11 mod 20 1 = 11 * 11 mod 20 11⁻¹ = 11

asdf: Dzieki! Mila − wiem, że można ustalić w pamięci..ale ja mam taki zwyczaj, że chcę zrozumieć jak coś działa, a nie jaki daje wynik . Nie zostawiam rzeczy z dobrą odpowiedzią, jeśli nie zrozumiem algorytmu.

Mila: Dobranoc.

asdf: Dobranoc