Zur Berchnung einer diophantischen Gleichung, wie sie beispielsweise bei der inversen Modulo Operation entsteht, wird der euklidische Algorithmus eingsetzt.
Allgemeine Form der Gleichung:
Damit die Gleichung lösbar ist, muss gelten:
einfache Euklidische Algorithmus
Um den ggt zu berechnen, wird als Linearkombination von aufgeschrieben, wobei der größere Wert auf der linken Seite stehen muss.
Für die Gleichung muss also die Annahme überprüft werden.
Diese obige Linearkombination kann wiederum in eine weiter Kombination aufgeteilt werden.
Die allgemeine Form für den zweiten Schritt würde also lauten:
Dabei ist der Rest der Gleichung. Sobald dieser beträgt, kann man den ggt in ablesen.
Die Berechnung würde dann folgendermaßen aussehen:
Also gilt:
erweiterte Euklidische Algorithmus
Für den erweiterten Euklidischen Algorithmus werden die vorherigen Schritte aus dem einfachen euklidischen Algorithmus benötigt. Beginnend beim vorletzten Schritt, werden die Zahlen ineinander eingesetzt, die bei allen Schritten aus dem einfachen euklidischen Algorithmus verwendet wurden. Dabei muss beachtet werden, dass zwei Faktoren während des Einsetzens niemals miteinander verrechnet werden sollten. Lediglich Klammern sollten aufgelöst werden. Es sollte nun die gelößte diophantische Gleichung am Schluss entstehen. Somit können und abgelesen werden.
Die ersten beiden Zeilen im erweiterten euklidischen Algorithmus lauten also;
Tabellenschreibweise
Das folgende Bild zeigt die Durchführung des euklidischen Algorithmus mithilfe einer Tabelle.
