Erweiterter euklidischer Algorithmus

Der erweiterte euklidische Algorithmus ist ein Algorithmus zur Berechnung der ganzen Zahlen xxx und yyy, so dass

ax+by=gcd(a,b)ax + by = \gcd(a,b)ax+by=gcd(a,b)

gegeben aaa und bbb.

Die Existenz solcher ganzen Zahlen wird durch das Lemma von Bézout garantiert.

Der erweiterte euklidische Algorithmus kann als der Kehrwert der modularen Potenzierung angesehen werden.

Durch Umkehrung der Schritte im euklidischen Algorithmus ist es möglich, diese ganzen Zahlen xxx und yyy zu finden. Die ganze Idee besteht darin, mit dem GCD zu beginnen und sich rekursiv rückwärts vorzuarbeiten. Dazu können wir die Zahlen als Variablen behandeln, bis wir einen Ausdruck erhalten, der eine Linearkombination unserer Ausgangszahlen ist. Wir werden dies mit dem obigen Beispiel tun.

Wir beginnen mit unserem GCD. Wir schreiben ihn in Form der beiden vorherigen Terme um:

2=26-2×12.2 = 26 – 2 \mal 12 .2=26-2×12.

Wir ersetzen für 121212, indem wir unsere vorherige Zeile (38=1×26+12)(38 = 1 \Zeit 26 + 12)(38=1×26+12) nehmen und sie in Begriffen von 12 schreiben:

2=26-2×(38-1×26).2 = 26 – 2 \Zeit (38 – 1\Zeit 26). 2=26-2×(38-1×26).

Sammeln Sie gleiche Terme, die 262626’s, und wir haben

2=3×26-2×38.2 = 3 \Zeiten 26 – 2 \Zeiten 38. 2=3×26-2×38.

Wiederholen Sie den Vorgang:

2=3×(102-2×38)-2×38.2 = 3 \Zeiten (102 – 2\Zeiten 38) – 2\Zeiten 38.2=3×(102-2×38)-2×38.

Das Endergebnis ist unsere Antwort:

2=3×102-8×38.2 = 3 \mal 102 – 8 \mal 38.2=3×102-8×38.

Damit sind xxx und yyy 333 und -8-8-8.

Finde zwei ganze Zahlen aaa und bbb so, dass 1914a+899b=gcd(1914,899).1914a + 899b = \gcd(1914,899). 1914a+899b=gcd(1914,899).

Wende zunächst den Euklidschen Algorithmus an, um den GCD zu finden:

1914=2×899+116899=7×116+87116=1×87+2987=3×29+0.\begin{aligned}1914 &= 2 \Zeiten 899 + 116 \\\899 &= 7 \Zeiten 116 + 87 \\\116 &= 1 \Zeiten 87 + 29 \\\87 &= 3 \Zeiten 29 + 0.\end{aligned}191489911687=2×899+116=7×116+87=1×87+29=3×29+0.

Der letzte von Null verschiedene Rest (GCD) ist somit 292929.Nun verwenden wir den erweiterten Algorithmus:

29=116+(-1)×8787=899+(-7)×116.\begin{aligned} 29 &= 116 + (-1)\times 87\87 &= 899 + (-7)\times 116.\end{aligned}2987=116+(-1)×87=899+(-7)×116.

Setzt man in der ersten Gleichung 878787 ein, so erhält man

29=116+(-1)×(899+(-7)×116)=(-1)×899+8×116=(-1)×899+8×(1914+(-2)×899)=8×1914+(-17)×899=8×1914-17×899.\begin{aligned}29&= 116 + (-1)\mal (899 + (-7)\mal 116) \\&= (-1)\Zeiten 899 + 8\Zeiten 116 \\\&= (-1)\Zeiten 899 + 8\Zeiten ( 1914 + (-2)\Zeiten 899 )\\\&= 8\Zeiten 1914 + (-17) \Zeiten 899 \\\&= 8\Zeiten 1914 – 17 \Zeiten 899.\end{aligned}29=116+(−1)×(899+(−7)×116)=(−1)×899+8×116=(−1)×899+8×(1914+(−2)×899)=8×1914+(−17)×899=8×1914−17×899.

Da wir nun den GCD als Linearkombination zweier ganzer Zahlen geschrieben haben, beenden wir den Algorithmus und schließen

a=8,b=-17. □ a = 8, b =-17. \ □ a = 8, b = 17. □