algorytm euklidesa Mądry uczeń: Witam, Jak używać odwróconego algorytmu euklidesa? Mam za zadanie obliczyć 2⁻¹ w ciele Z₁7. wiem że 17=2*8+1 8=8*1 jak to teraz odwrócić?

Mila: 17=8*2+1 koniec, masz resztę 1 1=17−8*2 −8 +17=9 odwrotna do 2 w Z₁₇ to liczba 9 9*2=18=1*17+1

Mądry uczeń: nie rozumiem jak przeszłaś z 2 linijki na 3 linijkę

Mila: W drugiej otrzymałam (−8) jako odwrotną do 2, przechodzę na dodatnią w arytmetyce modulo. Weź inny przykład: Odwrotna do 5 w arytmetyce Z₁₇

qwerty: 17=5*3+2 3=2*1+1 1=3−2*1 Wiem ze trzeba dalej coś pisać ale nie rozumien

qwerty: Jak cos to jedna osoba to pisze tylko nicki mam na komputerze i komórce zmienione

qwerty: nikt nie pomoże?

Mila: 5⁻¹ w Z₁₇⇔ 5x=1( mod17) 17=3*5+2 5=2*2+1 odwracamy: 1=5−2*2=5−2*(17−3*5)=1*5−2*17+6*5=7*5−2*17+6*5= =7*5−2*17 5⁻¹ to 7 w Z₁₇ sprawdzamy: 5*7=35=2*17+1