Gesucht ist der Kehrwert von 57 in Z100

Question

Kehrwert

Gegeben: 57 in \( \mathbb { Z } _ { 100 } \)

Gesucht: Kehrwert von 57 in \( \mathbb { Z } _ { 100 } \)

Ich habe 57 in Z100 gegeben und gesucht ist davon der Kehrwert gesucht.

Bedeutet das, dass a ∈ ℤ/100ℤ mit 57⋅a=1∈ℤ/100ℤ ist? Wenn ja, kennt jemand den Lösungsweg? Sitze seit 1 Stunde daran und komme auf keine Lösung.

Answer 1

Normalweise nennt man diese Zahl das multiplikativ Inverse, aber ja, genau das wird gesucht sein. Ein Ansatz der immer zum Ziel führt:

Berechne mit dem euklidischen Algorithmus: d=gg(57,100)

Wenn da 1 rauskommt, ist deine Zahl invertierbar. Dann kannst du mit dem erweiterten euklidischen Algorithmus eine Linearkombination des ggT berechnen:

d=ggT(57,100)=u*57+v*100

Wenn du diese jetzt modulo 100 betrachtest erhältst du

$$ u*57\equiv 1\mod 100$$

Also ist die Restklasse von u, das gesuchte Inverse.

Answer 2

Damit das Produkt bei Teilung durch 100 der Rest 1 hat, muss es bei Teilung durch 10 auch den Rest 1 lassen.

In Frage kommen damit nur 3, 13, 23, ..., 93.

Die 10 Werte kannst du durchprobieren.

Answer 3

Löse mit dem euklidischen Algorithmus die Kongruenz

        57x ≡ 1    mod 100.