Euklidischer Algorithmus: Multiplikative Inverse von 17 in Z113?

Question

Berechnen Sie mit dem Euklidischen Algorithmus ggT(113,17). Prüfen Sie, ob 17 in Z₁₁₃ eine Inverse besitzt und wenn ja, berechnen Sie 17^{-1} in Z₁₁₃ (Text!).

 

Die Aufgabe kann ich leider nicht lösen, da ich den euklidschen Algorithmus nie behandelt habe.

Answer 1

Du kannst dich aber fortbilden

https://de.wikipedia.org/wiki/Euklidischer_Algorithmus

ggT(113, 17)

113 - 6*17 = 11
17 - 11 = 6
11 - 6 = 5
6 - 5 = 1
5 - 5*1 = 0

ggT(113, 17) = 1

Multiplikativ Inverses

1 = 6 - 5

1 = 6 - (11 - 6) = - 11 + 2*6

1 = 6 - (11 - 6) = - 11 + 2*(17 - 11)

1 = - 3*11 + 2*17

1 = - 3*(113 - 6*17) + 2*17

1 = - 3*113 + 20*17

20 * 17 = 3*113 + 1

Also ist 17^{-1} = 20

Answer 2

(1)  113 : 17 = 6 Rest 11
⇒ 11 = 113 - 6·17

(2)  17 : 11 = 1 Rest 6
⇒ 6 = 17 - 1·11 = 17 - 1·(113 - 6·17) = -1·113 + 7·17

(3)  11 : 6 = 1 Rest 5
⇒ 5 = 11 - 1·6 = (113 - 6·17) - 1·(-1·113 + 7·17) = 2·113 - 13·17

(4)  6 : 5 = 1 Rest 1
⇒ 1 = 6 - 1·5 = (-1·113 + 7·17) - 1·(2·113 - 13·17) = -3·113 + 20·17.

Daraus folgt  ggT(113,17) = 1  und  17^-1 = 20  in  ℤ₁₁₃.