Teilbarkeit, Euklidische Algorithmus

Question

Ich verstehe die Aufgabe nicht und habe keine Ahnung wie man es ausrechnen soll. Waere dankbar wenn jemand mir hilft.

Bestimmen Sie das multiplikativ Inverse von 17 in Z/71Z = {0, 1, . . . , 70}. 
Hinweis: Es kann der Euklidische Algorithmus verwendet werden.

Comments

Weisst du, was der euklidische Algorithmus ist? Hast du damit schon mal gerechnet? 

Answer 1

wenn x das gesuchte Inverse ist, gilt ja 

x*17 ≡  1   mod 71 

bzw 

x*17 = n*71  + 1 

bzw

x*17 - n*71 = 1

Und weil ggt(71;17) = 1 kannst du

x und n bestimmen wie im Beispiel

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