Rozszerzony algorytm euklidesa qwerty: Witam. na czym polega rozszerzony algorytm euklidesa? zakładałem już temat, ale nikt nie chce pomóc, więc może w tym ktoś mi pomoże. np trzeba obliczyć 7⁻¹ w ciele Z₃₁. wiem jak się liczy do tego momentu 31=4*7+3 4=3*1+1 ale później to trzeba odwrócić, a tu już nie wiem jak dalej. Czy ktoś krok po kroku wytłumaczy prostym językiem?

qwerty:

Mila: Już jestem. 7⁻¹ w Z₃₁ Masz odpowiedzieć na pytanie , jaką liczbą jest x, aby było spełnione równanie w Z₃₁ 7*x=1(mod31) 31=4*7+3 7=2*3+1 Odwracamy: 1=7−2*3=7−2*(31−4*7)=1*7−2*31+8*7=9*7−2*31 7⁻¹=9 w Z₃₁ spr. 7*9=63=2*31+1

Janusz: 1=7−2*3=7−2*(31−4*7)=1*7−2*31+8*7,=9*7−2*31 nie wiem jak do tego na czerwono dojść, dlaczego jest 7−2*(31−4*7)

qwerty: po głębszym przeanalizowaniu chyba zrozumiałem: spróbuję rozwiazać to na przykłdzie 12⁻1 w ciele Z₂₉ 29=12*2+5 12=5*2+2 5=2*2+1 odwracam 1=5−2*2=5−(12−5*2)*2=29−12*2−(12−(29−12*2)*2)*2=29−12*2−(12−29*2+12*4)*2= =29−12*2−12*2+29*4−12*8=−12*12+29*5 1=−12*12+29*5 mod29 z −12 = 17 12*17=204 mod29 z 204 = 1

Mila: za resztę 3 podstawiamy (31−4*7)

qwerty: mogłabyś zobaczyć post 20:50?

Mila:

Mila: Dobrze. −12+29=17 12⁻¹=17 w Z₂₉ 204=1(mod29)

qwerty: wielkie dzięki, męczyłem się z tym, ale dzięki tobie udało się to załapać

Mila: