modulo ala: jak się rozwiązuję takie równanie: 56x ≡ 23 mod 93 ?

Mariusz: 56⁻¹56 ≡ 56⁻¹23 mod 93 Szukasz elementu odwrotnego do 56 w ℤ₉₃ Nie dla każdego elementu z ℤ₉₃ istnieje element odwrotny bo 93 nie jest pierwsza ale dla 56 akurat istnieje bo NWD(56,93)=1 Przydatny będzie rozszerzony algorytm Euklidesa Pseudokod algorytmu Euklidesa masz w CLRS Introduction to Algorithms (fe 3rd edition)

jc: nwd(23,93)=1 Algorytm Euklidesa 93=2*56−19 56=3*19−1 1=3*19−56=3*(2*56−93)−56=5*56−3*93 5*56 = 1 (mod 93) 5*23=115=22 (mod 93) 56*22=23 (mod 93)

Mariusz: jc to sprawdzamy nwd(23,93)=1 ? Mnie się wydawało że nwd(56,93)=1 aby upewnić się że można policzyć element odwrotny

jc: Mariusz, dobrze Ci się wydawało. Ja się pomyliłem. Ważne, aby nwd(56,93)|23 i tak faktycznie jest.