Znaleść liczbę odwrotną do m modulo p ,gdzie: Bartikooo: m=21,p=8

ICSP: 21 = 2*8 + 5 8 = 5 + 3 5 = 3 + 2 3 = 2 + 1 1 = 3 − 2 = = 3 − (5 − 3) = 2*3 − 5 = 2(8 − 5) − 5 = 2*8 − 3*5 = 2*8 − 3(21 − 2*8) = = 8*8 − 3*21 8⁻¹ = 8

Bartikooo: a co kiedy m=8,p=21?

chichi: @Bartikooo @ICSP właśnie zrobił przykład dla 8 mod 21, zamiast 21 mod 8

Mila: 1) Mały moduł, to możesz spróbować na piechotę. 2) Rozszerzony algorytm Euklidesa. 21=2*8+5 8=5*1+3 5=3*1+2 3=2*1+1 1=3−2*1=3−1*(5−3*1)=3−5*1+3*1=3*2−5=(8−5*1)*2−5= =8*2−5*3=8*2−(21−2*8)*3=8*2−3*21+6*8=8*8−3*21 21⁻¹≡₈(−3)≡₈≡5 5*21=105 =13*8+1

chichi: 21 mod 8 ≡ 5 mod 8 5x ≡ 1 mod 8 5*3 ≡ 7 mod 8 ≡ −1 mod 8 5*3 ≡ −1 mod 8 / *(−1) 5*(−3) ≡ 1 mod 8 ⇒ 5*5 ≡ 1 mod 8 ⇒ 5⁻¹ ≡ 5 mod 8

ICSP: Fakt. Z******m.