Tumblelog by Soup.io
Newer posts are loading.
You are at the newest post.
Click here to check if anything new just came in.
wizard23
19:46
Wir wollen die Inverse von 5 modulo 48 berechnen. (Sie tritt auf, wenn in der Animation p = 5 , q = 13 und a = 5 gewählt wird). Dazu schreiben wir zunächst den euklidischen Algorithmus auf, so als wollten wir den größten gemeinsamen Teiler dieser beiden Zahlen ermitteln. Da 5 und 48 teilerfremd sind, wissen wir natürlich, dass dabei ggT(485) = 1 herauskommen muss:

Der erweiterte euklidische Algorithmus besteht nun darin, ausgehend von der vorletzten Zeite, diese Rechenschritte "von unten nach oben" in der folgenden Weise aufzurollen, indem die einzelnen Zeilen nach den Resten aufgelöst und diese nacheinander eingesetzt werden:

Beachte, dass dabei zwar alle aufretenden Klammern ausmultipliziert, nicht aber alle Produkte ausmultipliziert werden! Damit ist gezeigt, dass
2 · 48 - 19 · 5  =  1
gilt, woraus
-19 · 5 mod 48  =  1
folgt. Nun haben wir die gesuchte Inverse schon fast gefunden. Da sie positiv und kleiner als 48 sein soll, addieren wir auf der linken Seite noch 48 · 5 (was auf der rechten Seite nichts ändert, da wir modulo 48 rechnen) und erhalten
29 · 5 mod 48  =  1.
Unser Resultat lautet daher:
5-1 mod 48  =  29.
Der erweiterte euklidische Algorithmus

Don't be the product, buy the product!

Schweinderl