Artikel

1.6: Der euklidische Algorithmus


In diesem Abschnitt beschreiben wir eine systematische Methode, die den größten gemeinsamen Teiler zweier ganzer Zahlen bestimmt. Diese Methode wird Euklidischer Algorithmus genannt.

[lem1] Wenn (a) und (b) zwei ganze Zahlen sind und (a=bq+r) wobei auch (q) und (r) ganze Zahlen sind, dann gilt ((a, b)=(r,b)).

Beachte, dass nach Satz 8 ((bq+r,b)=(b,r)) gilt.

Das obige Lemma führt zu einer allgemeineren Version davon. Wir präsentieren nun den Euklidischen Algorithmus in seiner allgemeinen Form. Es besagt, dass der größte gemeinsame Teiler von zwei ganzen Zahlen der letzte von Null verschiedene Rest der aufeinanderfolgenden Division ist.

Seien (a=r_0) und (b=r_1) zwei positive ganze Zahlen mit (ageq b). Wenn wir den Divisionsalgorithmus nacheinander anwenden, um zu erhalten, dass [r_j=r_{j+1}q_{j+1}+r_{j+2} mbox{wo} 0leq r_{j+2 }

Durch Anwendung des Divisionsalgorithmus sehen wir, dass [egin{aligned} r_0&=&r_1q_1+r_2 0leq r_2

Wir finden den größten gemeinsamen Teiler von (4147) und (10672):

Beachten Sie, dass [egin{aligned} 10672&=&4147cdot 2+2378, 4147&=&2378cdot 1+1769, 2378&=&1769cdot 1+609, 1769&=&609cdot 2 +551 , 609&=& 551cdot 1+58, 551&=&58cdot 9+ 29, 58&=&29cdot 2,end{ausgerichtet}] Daher ((4147,10672) =29.)

Wir verwenden nun die Schritte des euklidischen Algorithmus, um den größten gemeinsamen Teiler zweier Ganzzahlen als Linearkombination der beiden Ganzzahlen zu schreiben. Das folgende Beispiel bestimmt tatsächlich die Variablen (m) und (n), die in Satz [thm9] beschrieben sind. Der folgende Algorithmus kann durch eine allgemeine Form beschrieben werden, aber der Einfachheit der Ausdrücke halber werden wir ein Beispiel präsentieren, das die Schritte zeigt, um den größten gemeinsamen Teiler von zwei ganzen Zahlen als Linearkombination der beiden ganzen Zahlen zu erhalten.

Drücken Sie 29 als Linearkombination von (4147) und (10672) aus:

[egin{ausgerichtet} 29&=&551-9cdot 58, &=& 551-9(609-551cdot 1), &=& 10.551-9.609, &=& 10cdot (1769-609cdot 2)-9cdot 609, &=& 10cdot 1769-29cdot 609, &=& 10cdot 1769-29(2378-1769cdot 1), &=& 39cdot 1769-29cdot 2378, &=& 39(4147-2378cdot 1)-29cdot 2378, &=& 39cdot 4147-68cdot 2378, &=& 39cdot 4147-68(10672-4147cdot 2), &=& 175cdot 4147-68cdot 10672,end{ausgerichtet}]

Als Ergebnis sehen wir (29=175cdot 4147-68cdot 10672).

Übungen

  1. Verwenden Sie den euklidischen Algorithmus, um den größten gemeinsamen Teiler von 412 und 32 zu finden und ihn durch die beiden ganzen Zahlen auszudrücken.
  2. Verwenden Sie den euklidischen Algorithmus, um den größten gemeinsamen Teiler von 780 und 150 zu finden und ihn durch die beiden ganzen Zahlen auszudrücken.
  3. Finden Sie den größten gemeinsamen Teiler von (70,98, 108).
  4. Seien (a) und (b) zwei positive gerade ganze Zahlen. Beweisen Sie, dass ((a,b)=2(a/2,b/2).)
  5. Zeigen Sie, dass, wenn (a) und (b) positive ganze Zahlen sind, wobei (a) gerade und (b) ungerade ist, dann ((a,b)=(a/2,b) .)

MAT 112 Antike und Gegenwartsmathematik

Wir formulieren einen Algorithmus zur Berechnung der größten gemeinsamen Teiler, der der Strategie folgt, die wir in Beispiel 4.2.8 verwendet haben. Wie im Beispiel wenden wir wiederholt Satz 4.2.7 3.4 an, um die Berechnung von (gcd(a,b)) auf (gcd(afmod b, b) ext<.> ) Dadurch werden die Zahlen, deren größter gemeinsamer Teiler wir berechnen, in jedem Schritt kleiner, bis der Rest (afmod b) Null ist.

Der Algorithmus ist nach dem griechischen Mathematiker Euklid benannt, der ihn erstmals in Buch 7 seines Buches beschrieb Elemente (um 300 v. Chr.) [5]. Um die Darstellung des Algorithmus zu erleichtern, lassen wir als Eingaben nur natürliche Zahlen (positive ganze Zahlen) zu.

Im Video in Abbildung 4.3.1 stellen wir den Algorithmus vor und verwenden ihn, um die größten gemeinsamen Teiler zu finden.

Wir formulieren den Euklidischen Algorithmus in unserem Algorithmusformat.

Algorithmus 4.3.2 . Euklidischer Algorithmus.

Zwei natürliche Zahlen (a) und (b) mit (a>b)

Der größte gemeinsame Teiler (gcd(a,b)) von (a) und (b)

Im Algorithmus wird (r) in jeder Iteration der Schleife kleiner. Da (r) eine nicht negative ganze Zahl ist, muss sie schließlich Null werden. Der Algorithmus liefert also nach endlich vielen Schritten ein Ergebnis zurück.

Beispiel 4.3.3 . Größter gemeinsamer Teiler von (612) und (56).

Wir berechnen den größten gemeinsamen Teiler von (612) und (56) mit Algorithmus 4.3.2.

Da (r=52) ist die Aussage (r=0) falsch. Also setzen wir Punkt 1 fort mit:

Da (r=4) ist die Aussage (r=0) falsch. Also setzen wir Punkt 1 fort mit:

Da (r=0) ist die Aussage (r=0) falsch. Also setzen wir Punkt 1 fort mit:

Wir geben den Wert von (a) zurück, der (4 ext<.>) ist.

Wir haben festgestellt, dass der größte gemeinsame Teiler von (612) und (56) (4 ext<.>) ist.

Als nächstes wiederholen wir das vorherige Beispiel. Anstatt explizit aufzuschreiben, was in jedem Schritt passiert, schreiben wir den Wert jeder Variablen am Ende von Schritt 1 auf. Diese Notation ist besser geeignet, um die größten gemeinsamen Teiler von Hand zu berechnen.

Beispiel 4.3.4 . Größter gemeinsamer Teiler von (612) und (56) kompakt.

Wir berechnen den größten gemeinsamen Teiler von (612) und (56) mit Algorithmus 4.3.2. In der Tabelle geben wir die Werte der Variablen am Ende von Schritt 1 in jeder Iteration der Schleife an.

Schritt (R) (ein) (B)
Eingang (612) (56)
(1) (612fmod 56=52) (56) (52)
(1) (56fmod 52=4) (52) (4)
(1) (52fmod 4=0) (4) (0)
Ausgabe 4

Somit lautet die Ausgabe (gcd(612,56)=4 ext<.>)

Klicken Sie sich im interaktiven Algorithmus in Beispiel 4.3.5 durch die Schritte des euklidischen Algorithmus, um zu sehen, wie sich die Werte in den Variablen in jedem Schritt ändern.

Beispiel 4.3.5 . Euklidischer Algorithmus interaktiv.

Arbeiten Sie in Checkpoint 4.3.6 die Schritte des euklidischen Algorithmus durch, um einen größten gemeinsamen Teiler zu berechnen.

Kontrollpunkt 4.3.6 . Euklidischer Algorithmus.

Wir verwenden nun den euklidischen Algorithmus (Algorithmus 4.3.2), um zu beweisen, dass aufeinanderfolgende natürliche Zahlen teilerfremd sind.

Satz 4.3.7 .

Sei (n) eine natürliche Zahl. Dann ist (gcd(n,n+1)=1 ext<.>)

Nachweisen .

Sei (n) eine natürliche Zahl. Wir berechnen (gcd(n+1,n)) mit dem Euklidischen Algorithmus. mit Algorithmus 4.3.2. In der Tabelle geben wir die Werte der Variablen nach Schritt (1) in jeder Iteration der Schleife an.

Schritt (R) (ein) (B)
Eingang (n+1) (n)
(1) ((n+1)fmod n=1) (n) (1)
(1) (nfmod 1=0) (1) (0)
Ausgabe 1

Somit ist (gcd(n+1,n) = 1 ext<,>) und wir schließen, dass (n+1) und (n) teilerfremd sind.

Den Beweis des Satzes veranschaulichen wir an einem Zahlenbeispiel.

Beispiel 4.3.8 . (238) und (237) sind teilerfremd.

Wir berechnen den größten gemeinsamen Teiler von (238) und (237) mit Algorithmus 4.3.2. In der Tabelle geben wir die Werte der Variablen nach Schritt (1) in jeder Iteration der Schleife an.

Schritt (R) (ein) (B)
Eingang (238) (237)
(1) (238fmod 237=1) (237) (1)
(1) (237fmod 1=0) (1) (0)
Ausgabe (1)

Somit ist die Ausgabe (gcd(238,237)=1 ext<.>)

Berechnen Sie in Checkpoint 4.3.9 die größten gemeinsamen Teiler. Für einige der Probleme benötigen Sie den euklidischen Algorithmus nicht, können aber Eigenschaften der größten gemeinsamen Teiler anwenden, um die Berechnung zu beschleunigen.


Numerische Methoden für Wurzeln von Polynomen, Teil I

Beispiel 1

Nehmen Sie f ˜ 2 = 1 4 p ˜ ′ , und führen Sie einen EA in Gleitkomma-Arithmetik durch, indem Sie die Fehlergrenzen auf L.H.S. berechnen. von 2,37 wie wir gehen. Ergebnisse sind

Da unser Polynom ein Genauigkeitsniveau von 0,5 × 10 −7 hat, haben wir anscheinend ein nahezu gcd f ˜ 3 vom Grad 2.

Die in Abschnitt 4 beschriebene Folge P i = g c d ( p i − 1 , p ′ i − 1 ) wird nun ersetzt durch

wobei wir mit einem α-gcd einen nahe-gcd mit dem Genauigkeitsniveau α . meinen.

Hribernig zeigt, dass„Für |ζ| < 1, wenn (x - ) k–1 ist ein Faktor eines α-gcd von p ˜ und p ˜ ′ , dann hat p ˜ einen k-Cluster von Nullen mit Mittelpunkt ζ bei einer Genauigkeit von 3α”

Angenommen, nach Anwendung von 2.41 und der weiteren Berechnung von QJ und Q ˜ j wie in Abschnitt 4 haben wir

und überprüfe die Größe von r ˜ j . Wenn ‖ r ˜ j ‖ ≈ α , ( j = 1 , … , m ) , dann akzeptieren wir 2.42 als gültige Gruppierung der Nullstellen von p ˜ 1 in Cluster mit Genauigkeitsniveau α. Aber wenn ‖ r ˜ j ‖ >> (<<) α haben wir zu wenige (zu viele) Cluster, und wir müssen den Grad P ˜ l . senken (erhöhen) , d.h. wir müssen mindestens einen Schritt mehr (weniger) im stabilisierten EA machen, der P ˜ l . erzeugt

Wie in der Standardprozedur müssen, wenn einige der Q l den Grad > 1 haben, ihre ungefähren Nullstellen als Zentren der mehreren i-Cluster, die sie repräsentieren, gefunden werden. Diese Nullen werden bei der angegebenen Genauigkeit gut getrennt (sonst würden sie als eins Cluster) und sollte relativ einfach zu finden sein.


Die Behauptung ist falsch, wenn $K$ kein Feld ist:

Nehmen wir $P=2$ und $Q=2X$ in $mathbb Z[X]$ . Wenn $AP + BQ = 1$ ist, dann ist $2A(0)=1$ , was in $mathbb Z$ nicht passieren kann.

Die Behauptung ist falsch, wenn $K$ kein algebraisch abgeschlossenes Feld ist:

Nimm $P=X^2+1$ und $Q=X(X^2+1)$ in $mathbb R[X]$ . Wenn $AP + BQ = 1$ dann $(A+BX)(X^2+1)=1$ , was in $mathbb R[X]$ nicht passieren kann, da $X^2+1$ keine Einheit ist .

Die Behauptung ist wahr, wenn $K$ ein algebraisch abgeschlossener Körper ist.

In diesem Fall haben $P$ und $Q$ keine gemeinsamen Wurzeln, wenn $gcd(P,Q)=1$ weil die Irreduziblen in $K[X]$ genau die Polynome vom Grad $1$ sind, wenn $K$ ist ein algebraisch abgeschlossener Körper. Die Behauptung folgt dann aus dem erweiterten euklidischen Algorithmus.


1.6: Der euklidische Algorithmus

Der euklidische Algorithmus und das Lösen von Kongruenzen

Joseph Malkevitch
Fachbereich Mathematik und Informatik
York College (CUNY)
Jamaika, New York 11451


Wenn d der größte gemeinsame Teiler von zwei (positiven) ganzen Zahlen a und b ist, dann teilt d den Rest r, der sich aus der Division der kleineren von a und b durch die größere ergibt.

Der größte gemeinsame Teiler von 24 und 16 ist 8.

24 = 1(16) + 8. Daher ist der Rest, wenn 24 durch 16 geteilt wird, 8, was durch 8 teilbar ist.

Der größte gemeinsame Teiler von 100 und 60 ist 20.

100 = 1(60) + 40. Der Rest 40 ist durch 20 teilbar.

Die obige Tatsache bildet die Grundlage für den sogenannten Euklidischen Algorithmus zur Ermittlung des größten gemeinsamen Teilers zweier Zahlen. Der Algorithmus ist nach demselben Mathematiker Euklid benannt, der für seine Arbeiten in der Geometrie berühmt ist. Der Reiz dieses Algorithmus besteht darin, dass er nicht den größten gemeinsamen Teiler durch die Faktorisierung in Primzahlen findet. Die Faktorisierung großer Zahlen scheint ein sehr schwieriges Problem zu sein. Die genaue Rechenkomplexität des Factoring ist derzeit nicht bekannt, aber einer der am weitesten verbreiteten Kryptographie-Algorithmen (z. B. RSA, benannt nach den Informatikern Ronald Rivest, Adi Shamir und Leonard Adelman, die das 1978 veröffentlichte Verfahren entwickelten während sie am MIT studierten) hängt für seine Sicherheit von der Annahme ab, dass die Faktorisierung großer Zahlen sehr schwierig ist.

Gegeben a und b, dividiere den kleineren und den größeren, um einen Quotienten q und einen Rest r zu erhalten.

Unter der Annahme, dass b größer als a ist, gilt:

b = q(a) + r. Nun ist der größte gemeinsame Teiler von b und a gleich dem größten gemeinsamen Teiler von a und r.

Wenn wir den Vorgang für a und r (statt a und b) wiederholen, kommen wir schließlich zu einer Situation, in der der Rest Null ist. Es ist eine Eigenschaft des Divisionsalgorithmus, dass der Rest r, den wir erhalten, eine kleinere Zahl als b sein muss. Der größte gemeinsame Teiler ist der letzte von Null verschiedene Rest in diesem Prozess.

Finden Sie den größten gemeinsamen Teiler von 36 und 10.

Der letzte von Null verschiedene Rest ist 2, und daher ist der größte gemeinsame Teiler von 10 und 36 2.

Wenn d der größte gemeinsame Teiler von a und b ist, kann d in der Form geschrieben werden:


wobei x und y ganze Zahlen sind.

Insbesondere wenn zwei Zahlen relativ prim sind, d. h. ihr größter gemeinsamer Teiler ist 1, dann können wir daraus schließen:

für einige ganze Zahlen x und y.

Lassen Sie uns die Werte x und y für das Beispiel 3 finden. In diesem Beispiel haben wir gesehen, dass der größte gemeinsame Teiler von 36 und 10 2 ist.


Wir sehen aus Gleichung (4), dass der größte gemeinsame Teiler von 36 und 10 2 ist und dass:

Aber wir wissen aus Gleichung (3), dass 4 = 1(10) - 1(6), also können wir den Wert 4 in Gleichung (5) durch 1 (10) - 1(6) ersetzen, um zu erhalten:

2 = (1)(6) - 1 (1(10) - 1(6)) = (1)(6) -1(10) + 1(6) = 2(6) - 1 (10). (6)

Aber wir wissen aus Gleichung (2), dass 6 = 1(36) - 3(10), also können wir den Wert 6 in Gleichung (6) durch 1(36) - 3(10) ersetzen, um zu erhalten:

2 = 2(1(36) - 3(10)) -1(10) = 2(36) - 6(10) - 1(10) = 2(36) - 7(10).

Daher ist der gesuchte Wert von x 2 und der gesuchte Wert von y ist -7, und tatsächlich haben wir mit diesen Werten 2 = 36x + 10y.

Diese Methode des Zurückverfolgens durch die Schritte, die verwendet werden, um die gcd von zwei ganzen Zahlen zu finden, kann immer verwendet werden, um die Werte der ganzen Zahlen x und y in Satz 1 zu finden.

Nehmen wir nun an, wir haben eine Kongruenz:

unter der Annahme, dass a und p relativ prim sind, können wir zwei ganze Zahlen s und t finden, so dass + pt = 1 gilt. Nehmen wir diese Kongruenz modulo p, so erhalten wir:

Wenn wir also x auf den Wert von bs setzen, haben wir einen Wert für x gefunden, der die obige Kongruenz (*) löst.

Was noch zu tun bleibt, ist, einen Algorithmus zum Lösen von Kongruenzen zu haben, bei denen der Modul eine Primzahl ist, um die Werte für x und y in der obigen Gleichung (1) zu finden. Dazu verwenden wir den euklidischen Algorithmus. Anstatt zu beschreiben, was im Allgemeinen passiert, werde ich es mit einigen typischen Beispielen illustrieren.

Angenommen, man möchte die Kongruenz lösen:

Finden Sie als ersten Schritt den größten gemeinsamen Teiler von 23 und 11 mit dem Euklidischen Algorithmus:

11 = 1(11) + 0, also ist der gcd 1.

Aus der obigen Gleichung sehen wir, dass 1 = (1)(23) + (-2)11. Modulo 23 dieser Gleichungen ergibt (-2)(11) ≡ 1 mod 23. Somit löst x = -2 die Kongruenz. Da wir die Antwort als Wert von 0 bis 22 schreiben wollen, sehen wir, dass -2 ≡ 21 mod 23, also x= 21 die Lösung ist.

Betrachten Sie nun die Kongruenz:

Als ersten Schritt lösen wir die Kongruenz: 16x ≡ 1 mod 29

Wir können also schreiben, dass 1 = 1(13) + (-4)(3) ist.

Einsetzen in diese Gleichung unter Verwendung der Tatsache, dass aus (3), 3 = 16 -1(13) wir erhalten:

1 = 1(13) + (-4)(16-1(13)) = 5(13) + (-4)(16) (5)

Unter Verwendung von (2) (von dem wir wissen, dass 13 = 29 -1(16) ist) können wir 13 in (5) ersetzen:

Diese letzte Gleichung modulo 29 ergibt:

Der gesuchte Wert von x ist also -9, was modulo 29 zu 20 kongruent ist.

Da wir nun wissen, dass 16(20) kongruent zu 1 modulo 29 ist, können wir beide Seiten dieser Kongruenz mit 5 multiplizieren, um zu erhalten, dass 100(16) kongruent zu 5 modulo 29 ist. Da 100 kongruent zu 13 modulo 29 ist, schließen wir, dass 13 ist die Lösung der Kongruenz, die wir lösen wollten:

Sie sollten überprüfen, dass 16(13) - 5 bei der Division durch 29 tatsächlich einen Rest von Null hinterlässt.

Die obigen Methoden können erweitert werden, um Kongruenzen zu lösen, bei denen p keine Primzahl ist. Der Vorteil der Arbeit mit einem Primzahlmodul besteht darin, dass wir, solange a in (*) kein Vielfaches von p ist, immer eine eindeutige Lösung für die Kongruenz mit einem Wert von x mit einem Wert zwischen 0 und (p-1) finden können. .


Math 321 Unterrichtsnotizen

Dann ist (gcd(a,b) = r_n ext<,>) der letzte von Null verschiedene Rest.

Beispiel 3.3.7 .

Hier ist ein vollständig ausgearbeitetes Beispiel, das zeigt, wie der Algorithmus ausgeführt wird, um (gcd(7592, 5913)) zu finden.

Nach dem Euklidischen Algorithmus ist der letzte von Null verschiedene Rest der gcd, also (gcd(7592, 5913) = 73 ext<.>)

Beispiel 3.3.8 .
Vorschlag 3.3.9 . Bézouts Lemma.

Wenn (a und b) positive ganze Zahlen sind, dann gibt es ganze Zahlen (s und t) mit ()

Definition 3.3.10 .

Wir nennen (s und t) im Satz über (a und b ext<.>)

Beispiel 3.3.11 . Zurück Ersatz.

Wir können den euklidischen Algorithmus umkehren, um die Bézout-Koeffizienten zu finden, ein Prozess, den wir nennen werden. Wir lösen jede Gleichung im euklidischen Algorithmus für den Rest und ersetzen und kombinieren wiederholt ähnliche Terme, bis wir die gcd erhalten, die als a der beiden ursprünglichen Zahlen geschrieben ist, in diesem Fall (73 = 7592s + 5913t)

Ersetzen und Kombinieren ähnlicher Begriffe:

Beispiel 3.3.12 .

Drücken Sie die gcd von 168 und 525 als Linearkombination dieser Zahlen aus.

Beispiel 3.3.13 .
  1. Verwenden Sie den euklidischen Algorithmus, um (gcd(4147, 10672) ext<.>) zu finden.
  2. Verwenden Sie die Rücksubstitution (kehren Sie die Schritte des euklidischen Algorithmus um), um den größten gemeinsamen Teiler von 4147 und 10672 als Linearkombination dieser Zahlen zu schreiben.

Übungen 3.3.1 Übungen

Finden Sie die gcd über den euklidischen Algorithmus und verwenden Sie dann die Rücksubstitution, um die gcd als Linearkombination dieser Zahlen zu schreiben:

  1. (displaystyle gcd(36, 48) )
  2. (displaystyle gcd(21, 724) )
  3. (displaystyle gcd(60, 97) )
  4. (displaystyle gcd(5, 26) )

Verwenden Sie eine beliebige Methode, um den größten gemeinsamen Teiler von 412 und 32 zu finden.

(gcd(412, 32) = 4 ext<.>) Wir können es als Linearkombination korrigieren: (4=412(-1) + 32(13))

Verwenden Sie eine beliebige Methode, um den größten gemeinsamen Teiler von 780 und 150 zu finden.

(gcd(780, 150) = 30 ext<.>) Wir können die gcd als Linearkombination aufrichten (30=780(1) + 150(-5))


Nachweisen

. .

Lösen für Mit der vorletzten Gleichung erhalten wir:

weil durch den euklidischen Algorithmus,

Gl. 4         

Jetzt lass uns auflösen für auf die gleiche Weise:

Gl. 5         

Ersatz Gl. 5 hinein Gl. 4 :

Jetzt können Sie sehen, dass gcd(a, b) durch eine Linearkombination von ausgedrückt wird und . Wenn wir diesen Vorgang fortsetzen, indem wir die vorherigen Gleichungen aus der obigen Liste verwenden, könnten wir eine Linearkombination von erhalten und mit vertreten und vertreten . Wenn wir so weitermachen, bis wir die erste Gleichung treffen, können wir gcd(a, b) als Linearkombination von a und b ausdrücken, was wir auch beabsichtigen.


Euklidischer Algorithmus und erweiterter euklidischer Algorithmus machen es elegant einfach, die beiden Bézout-Koeffizienten zu berechnen.


Euklidischer Algorithmus

Laden Sie das Video von iTunes U oder dem Internetarchiv herunter.

PROFESSOR: Der größte gemeinsame Teiler zweier Zahlen ist leicht zu berechnen. Und dieser Faktor wird eine entscheidende Rolle bei der Nummer drei spielen, die wir entwickeln werden, und bei den Eigenschaften einiger der modernen Codes, die auf der Zahlentheorie basieren. Die effiziente Methode zur Berechnung der GCD zweier Zahlen basiert auf einem klassischen Algorithmus, der mehrere tausend Jahre alt ist, der als Euklidischer Algorithmus bekannt ist. Und lassen Sie uns beschreiben, wie es jetzt funktioniert.

Der euklidische Algorithmus basiert also auf dem folgenden Lemma, das wir Restlemma nennen, und es sagt, wenn a und b zwei ganze Zahlen sind, dann ist der größte gemeinsame Teiler von a und b der gleiche wie der größte gemeinsame Teiler von b, und der Rest von a geteilt durch b – vorausgesetzt natürlich, dass b nicht 0 ist, weil Sie sonst nicht durch b teilen können.

Okay, wie ist das zu verstehen? Warum ist das wahr? Nun, es ist eigentlich ein sehr einfacher Beweis. Denken Sie daran, dass Sie nach dem sogenannten Divisionsalgorithmus – oder es ist wirklich ein Theorem –, wenn Sie a durch b teilen und eine ganzzahlige Division durchführen, das bedeutet, dass Sie im Quotienten einen Quotienten von a dividiert durch b finden, und ein Rest. Und der Quotient hat die Eigenschaft, dass q mal b plus Rest gleich a ist. Der Rest ist immer kleiner als a. Dies ist der Bereich von 0 bis, jedoch nicht einschließlich, a.

OK, wenn Sie sich diesen einfachen Ausdruck ansehen, wird deutlich, dass wenn Sie einen Teiler von zwei von drei dieser Terme haben, dann wird der dritte Term geteilt. Wenn Sie also beispielsweise einen Teiler von b und r haben, hat die Summe dieser beiden Dinge auch denselben Teiler, was bedeutet, dass a diesen Teiler hat. Wenn etwas sowohl a als auch b teilt, dann teilt es r. Und wenn es b und r teilt, teilt es a. Und das bedeutet, dass a und b und b und r genau die gleichen Teiler haben. Sie haben nicht nur den gleichen größten gemeinsamen Teiler, alle ihre Teiler sind gleich. Der Größte ist also offensichtlich derselbe. Und das beweist dieses Schlüsselrestlemma.

Nun, das Restlemma gibt uns jetzt eine sehr schöne Möglichkeit, die GCD zu berechnen. Und hier ist ein Beispiel. Angenommen, ich möchte die GCD von 899 und 493 berechnen. A ist 899, b ist 493. Nun, also ich möchte diese GCD, 899 von 493. Nun, nach dem Restlemma, wenn ich 899 durch 493 dividiere, erhalte ich a Quotient von 1 und einem Rest von 406. Das bedeutet, dass 899 und 493 die gleiche GCD wie 493 und 406 haben. Das ist die ursprüngliche Zahl b und der neue Rest 406.

Aber jetzt kann ich 493 durch 406 teilen. Ich erhalte einen Quotienten von Null und einen Rest von 87. Also haben 406 und 87 die gleiche GCD. Wenn ich 406 durch 87 dividiere, erhalte ich, dass 87 und 58 die gleiche GCD haben. Wenn ich 87 durch 58 dividiere, erhalte ich, dass 58 und 29 die gleiche GCD haben. Und jetzt gewinne ich, denn schau, wenn ich 58 durch 29 dividiere, erhalte ich einen Rest von 0. Und die GCD von allem und 0 ist das Ding. Die GCD von 29 und 0 ist also 0. Ich denke, die einzige Ausnahme ist die GCD von 0 und 0, die nicht definiert ist. Aber wenn es nicht 0 ist, dann ist die GCD von x und 0 x.

Und da ist es. Ich habe also gerade herausgefunden, dass die GCD von 899 und 493 29 ist. Und dies ist ein ziemlich schneller Algorithmus, weil ich die Zahlen, die ich habe, immer wieder durcheinander teile, und es wird schnell klein. Wir werden in einer Minute genauer sein.

OK, es ist eine gute Übung im Denken von Zustandsautomaten und in der Programmverifikation, den euklidischen Algorithmus neu zu formulieren oder explizit als Zustandsautomat zu formulieren. Es ist eine sehr einfache Art von Zustandsmaschine. Die Zustände dieser Zustandsmaschine des euklidischen Algorithmus sind Paare von nicht-negativen ganzen Zahlen. Die Zustände sind also n durch n, das kartesische Produkt der nicht-negativen ganzen Zahlen, mit sich selbst. Der Startzustand wird das Paar a, b sein, dessen GCD ich berechnen möchte.

Und die Übergänge wenden einfach immer wieder das Restlemma an. Wenn ich mich nämlich im Zustand x, y befinde, in dem Sie sich x als und y als die GCD vorstellen, die ich zu berechnen versuche, wandele ich einfach x und y in y um und den Rest von x dividiere durch y. Und das mache ich so lange, wie y nicht 0 ist.

OK, sehr einfacher Zustandsautomat - wirklich nur eine Übergangsregel. Nun, nach dem Lemma bleibt die GCD tatsächlich konstant, da ich die GCD von x und y durch die GCD von y und den Rest von x dividiert durch y ersetze. Dieser Übergang bewahrt die GCD, die im Registerpaar x und y übrig ist. Was wir also sagen können ist, dass, da sich die GCD von x und y von einem Schritt zum nächsten nicht ändert, wir sagen können, dass die GCD von x und y an jedem Punkt gleich ihrem ursprünglichen Wert ist, der der GCD von a . ist und B.

Mit anderen Worten, diese Gleichung, GCD von x und y im aktuellen Zustand ist gleich GCD von a und b, die GCD von a und b, mit der wir begonnen haben, ist eine erhaltene Invariante des Zustands. p eines Zustands xy, die Eigenschaft, dass GCD von x und y die ursprüngliche GCD ist, ist also eine erhaltene Invariante des Zustandsautomaten. Außerdem ist p von start trivialerweise wahr, denn am Anfang sind x und y a gleich b. p von x und y sagt also nur, dass die GCD von a und b gleich der GCD von a und b ist.

Cool. Ich habe also festgestellt, dass diese Eigenschaft am Anfang wahr ist und von den Übergängen beibehalten wird. Das Invarianzprinzip sagt mir also, dass, wenn das Programm stoppt, die GCD von x und y beim Beenden gleich der tatsächlichen GCD ist, die ich möchte. Und damit können wir teilweise Korrektheit beweisen. Die Behauptung ist, dass wenn dieses Programm terminiert – wir haben noch nicht festgestellt, dass dies der Fall ist – aber bei einer Beendigung, falls vorhanden, behaupte ich, dass x darin belassen wird – dass die GCD von a und b im Register x gelassen wird. Der Wert von x am Ende wird der GCD von und und b sein.

Nun, warum ist das so? Nun, sehen Sie sich die Terminierung an, was wir wissen ist, dass y 0 ist. Dies ist der einzige Weg, um diese Prozedur zu stoppen, da ansonsten die Übergangsregel anwendbar ist. Das heißt, wenn y am Ende gleich 0 ist, haben wir, da y 0 ist, GCD von x und y gleich der GCD von x und 0. Und das ist gleich x, wiederum angenommen, x ist positiv , oder nicht 0.z

Also ist x die GCD von x und y. Und nach der Invariante ist die GCD von x und y gleich der GCD von a und b. Also habe ich diese kleine Tatsache bewiesen. Diese Prozedur berechnet die GCD von a und b korrekt und belässt die Antwort im Register x, wenn sie terminiert. Nun, natürlich endet es, und es endet schnell. Mal sehen warum.

Beachten Sie, dass wir bei jedem Übergang x durch y und y durch den Rest von x dividiert durch y ersetzen. Nehmen wir der Einfachheit halber an, dass der [? Paarungen, ?] y dass x der größere ist. Es gibt also zwei Fälle, warum diese Zahlen schnell klein werden. Der erste Fall ist, dass y kleiner als x über 2 oder kleiner oder gleich x über 2 ist. Nun, da Sie in diesem Schritt x durch y ersetzen werden, bedeutet dies, dass Sie x durch . ersetzen etwas, das weniger als halb x ist. Also wird x in diesem Schritt halbiert.

Was ist, wenn y groß ist? Nun, wenn y größer als x über 2 ist, dann ist der Rest von x geteilt durch y einfach x minus y. Und es wird kleiner als x über 2 sein. Aber das wird der Wert von y nach dem nächsten Schritt sein. y wird also entweder in diesem Schritt oder im nächsten Schritt halbiert, wenn es durch den Rest von x und y ersetzt wird. Und das Nettoergebnis ist, dass y bei jedem zweiten Schritt halbiert oder noch kleiner wird, was bedeutet, dass dieses Verfahren nicht länger als das Doppelte des Logarithmus zur Basis 2 des ursprünglichen Wertes von y fortgesetzt werden kann, was ist b Anzahl der Schritte, denn so viele Hälften kannst du machen, bevor du anfängst, 0 zu treffen.

Wir haben also gerade gezeigt, dass dieses Verfahren in logarithmischen Schritten gilt, was der Aussage entspricht, dass es um die Länge von b im Binärformat und noch weniger Schritte als die Länge von b im Dezimalformat geht. Der GCD-Algorithmus ist wirklich sehr effizient.


1.6: Der euklidische Algorithmus

Hier ist ein Link, der den Algorithmus beschreibt. Hier noch ein Link mit weiteren Informationen. Wenn Sie einige weitere Beispiele "machen" möchten, hat Paul Garrett von der University of Minnesota eine Seite mit sichtbarem euklidischem Algorithmus, auf der Sie weitere Beispiele angeben und die Arbeit des Algorithmus sehen können.

In der letzten Stufe, wenn r = 0, sehen wir, dass das "letzte b" das letzte a teilen muss. Gehen Sie entlang der Gleichungskette rückwärts (a=q·b+r), und Sie werden sehen, dass bei jedem Schritt das "finale b" jeden der Teile der Gleichung teilt. Daher muss das "finale b" ein Teiler des anfänglichen a und des anfänglichen b sein.

Der erweiterte euklidische Algorithmus

  • Dividiere 210 durch 45 und erhalte das Ergebnis 4 mit Rest 30, also 210=4·45+30.
    30=1·210-4·45.
  • Teile 45 durch 30 und erhalte das Ergebnis 1 mit Rest 15, also 45=1 45·30+15.
    15=45-1·30=45-1·(1·210-4·45)=-1·210+5·45

Der erweiterte euklidische Algorithmus hat einen sehr wichtigen Zweck: das Finden multiplikativer Inversen mod P. Wähle eine Primzahl, P: wie wäre es mit 97. Ich weiß, dass 97 eine Primzahl ist, weil 2 und 3 und 5 und 7 und sogar 11 keine Faktoren von 97 sind, und ich muss nur die Division durch Primzahlen bis zur Quadratwurzel von 97 überprüfen.

  • 97=4·20+17
  • 20=1·17+3
  • 17=5·3+2
  • 3=1·2+1
  • 17=1·97-4·20
  • 20-1·17=3 also 3 =1·20-1·17=1·20-(1·97-4·20)= -1·97+5·20
  • 17=5·3+2 so 2 =17-5·3=(1·97-4·20)-5(-1·97+5·20)= 6·97-29·20
  • 1 =3-2=(-1·97+5·20)-(6·97-29·20)= -7·97+34·20

Ausübung
Finden Sie die multiplikative Inverse von 60 mod 97 von Hand. Wie ich im Unterricht erwähnt habe, ist es gut genug, nur eine dieser Berechnungen "von Hand" durchzuführen. Hier ist ein Link zur Antwort.

Der erweiterte euklidische Algorithmus ist einfach auf einem Computer zu implementieren und die benötigte Speichermenge ist nicht groß. Der Algorithmus läuft sehr schnell. Zum Beispiel betreibe ich derzeit eine Kopie von Ahorn in einem anderen Fenster auf einem PC, der weder sehr schnell ist noch viel Speicher hat. Ich habe gerade eine Primzahl mit 100 Dezimalstellen, P, ausgewählt und die multiplikative Umkehrung einer Zahl mit 50 Dezimalstellen mod P gefunden. Das heißt, die Berechnung dauerte weniger als 0,01 Sekunden!