Wie kann man das modulare Inverse bestimmen?

...komplette Frage anzeigen

1 Antwort

Es könnte sich um die Lösung x der Gleichung

a * x = 1

handeln, wobei a, x und 1 Elemente eines Restklassenrings Z/n (lies: "Z modulo n) handeln. x heißt dann das multiplikativ Inverse von a. Das Zeichen " = " sollte eigentlich drei statt zweier Striche enthalten und ist dann nicht "gleich", sondern "kongruent" zu lesen.

A. Grundinfos über Restklassenringe, falls erforderlich, in >http://de.wikipedia.org/wiki/Restklassenring . Das mulitplikativ Inverse von a aus Z/n existiert genau dann, wenn die natürlichen Zahlen a und n keinen gemeinsamen Teiler haben.

B. Die erweiterete euklidsche Division (zur Bestimmung des Inversen) finde ich recht umständlich in der Wikipedia dargestellt. Eigene Version, wenn du weißt, was eine euklidsche Division ist (das ist einfach):

In a0, a1, ai, bi, bn, an, bk, ak-2, ak-1 ist 0, 1, i, n, k, k-2, k-1 ein Index.

Die mit a0 = t, a1 = a beginnende Euklidsche Division erzeugt eine geordnete Menge M, deren kleinstes Element an = 1 ist. Eine zweite geordnete Menge wird erzeugt mit der Rekursion

bn = an, bk-1 = (-bk * ak-2 + 1) / ak-1.

Dann ist b1 das Inverse von a

Beispiel:

ai 19 15 4 3 1

bi .....-5 4 -1 1

also ist -5 (kongruent 19 - 5 = 14) das multiplikativ Inverse von 15 in Z/19, d.h. 15 * 14 - 1 ist ohne Rest durch 19 teilbar (ich weiß dies, ohne das Produkt bestimmt zu haben; es lässt sich aber im Kopf leicht nachrechnen.

C. Bei Bedarf kannst du auch einen Beweis zur Aussagen in B. bekommen.

Was möchtest Du wissen?