Wir wollen die Inverse von 5
modulo 48 berechnen.
(Sie tritt auf, wenn in der Animation 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: |