Inverse mit Euklid berechnen

Modulare Inverse · Abschnitt 10 von 64

Strategie

Bézout wird zur Inversenmaschine

Aus $ua+vm=1$ folgt modulo $m$ sofort $ua\equiv1$ . Der Koeffizient $u$ vor $a$ ist also die gesuchte Inverse.

Gelöstes Beispiel

Rückwärtseinsetzen ergibt $1=2\cdot43-5\cdot17$ . Daher ist $-5\equiv38\pmod{43}$ die Inverse von 17.

Checkliste

Typischer Fehler

In $1=ua+vm$ ist $u$ die Inverse von $a$ modulo $m$ . Der Koeffizient $v$ gehört zum Modul und verschwindet erst in der Kongruenz.