ciała Kontik: Zadałem pytanie na innym forum, ale może ktoś tutaj mi pomoże. http://forum.zadania.info/viewtopic.php?f=36&t=75464 Nie przepisuję tutaj bo jest tego sporo, a musiałbym skonwertować z Latexa, a tam wszystko dobrze widać.

Mila: Czego tam nie rozumiesz?

Kontik: Zadałem na dole pięć pytań. Proszę przynajmniej o odpowiedź na te obliczeniowe, chociaż bardzo byłbym wdzięczny za roztłumaczenie pozostałych.

Mila: Czy rozumiesz rozszerzony algorytm Euklidesa?

Kontik: Rozszerzony nie. Czy jest on potrzebny? Rozumiem taki jak jest opisany np. tutaj: http://www.math.edu.pl/narzedzia.php?opcja=algorytm-euklidesa

Mila: Masz rozwiązać równanie w Z₂₃ 17x=−10( mod23)⇔ 17x=(−10+23)(mod(23)⇔ 17x=13(mod 23)⇔ szukasz liczby odwrotnej do 17 w Z₂₃, 17*17⁻¹=1 obliczysz 1x , a o to chodzi. Algorytm 23=17*1+6 17=6*2+5 6=5*1+1 odwracamy: 1=6−5*1=6−(17−2*6)=6−17*1+2*6=3*6−17*1=3*(23−17)−17*1=3*23−3*17−17=3*23−4*17 17⁻¹=−4 w Z₂₃ Wracamy do równania: 17x=13(mod23) /*(−4)⇔ −68x=−52(mod(23)⇔ (23*(−3)+1)x=(−3*23+17) (mod(23)⇔ 1x=17 (mod 23) Możesz to zapisać liczbę odwrotną inaczej: −4+23=19 17x=13(mod 23) /19 323x=247(mod23)⇔ (14*13+1)x=(10*23+17) (mod(23)⇔ 1x=17 spr 17*17=289=13+276=13+12*23=13(mod(23)) Jeśli cos niejasne, to pisz.

Mila: b) 7⁻¹ w Z₂₃ 23=7*3+2 7=2*3+1 odwracamy : 1=7−3*2=7−3*(23−7*3)=7−3*23+9*7=10*7−3*23 7⁻¹=10 w Z₂₃ Możesz dla takiej liczby obliczyć inaczej W₂₃={23,46,69, ...} 7*4=28=5(mod23) 7*5=35=12(mod23) itd . 7*10=70=69+1=3*23+1 odwrotna do 7 w Z₂₃ to liczba 10

Mila: 2) (b) Jeżeli p jest liczbą pierwszą, oraz a jest taką liczbą całkowitą, że liczby a i p są względnie pierwsze, to a^p−1 − 1 dzieli się przez p. p=23 liczba pierwsza NWD(23,3)=1 3²³⁻¹=1 mod(23)⇔ 3²²=1 (mod23) 3⁷²=(3²²)³*3³*3³=1*27*27=4₍₂₃₎*4₍₂₃₎=16₍₂₃₎

Mila: poprawka Zamiast: 4₍₂₃₎*4₍₂₃₎=16₍₂₃₎ Ma być : =4(mod(23))*4(mod(23))=16(mod(23))