Element odwrotny Qto: Wykorzystując algorytm Euklidesa, znajdź element odwrotny do k w Z_n. Z_n oznacza zbiór klas abstrakcji(reszt) z dzielenia przez n. a) n = 42, k = 8 b) n = 73, k = 14 c) n = 83, k = 11. Proszę o pomoc.

Adamm: a) NWD(42, 8) = NWD(2, 8) = 2 ≠ 1 element odwrotny nie istnieje b) NWD(73, 14) = NWD(3, 14) = 1 73=5*14+3 14=4*3+2 3=1*2+1 1=3−2 2=14−4*3 1=5*3−14 3=73−5*14 1=5*73−26*14 element odwrotny wynosi −26≡₇₃47 c) analogicznie

Mila: c) n = 83, k = 11 11x=1 (mod83) 83=7*11+6 11=1*6+5 6=5*1+1 Odwracamy algorytm 1=6−5*1=1*6−1*(11−1*6)=1*6−1*11+1*6=2*6−1*11=2*(83−7*11)−1*11= =2*83−14*11−1*11=2*83−15*11 −15 odwrotna do11w Z₈₃ −15+83=68 68 odwrotna do 11 w Z₈₃