Artikel

5.4: Größte gemeinsame Teiler - Mathematik


Gegeben zwei beliebige ganze Zahlen (a) und (b), ist eine ganze Zahl (c eq0) a gemeinsamer Teiler oder gemeinsamer Faktor von (a) und (b), wenn (c) sowohl (a) als auch (b) teilt. Sind außerdem (a) und (b) ungleich Null, dann gilt größter gemeinsamer Teiler, bezeichnet mit (gcd(a,b)), ist definiert als der größte gemeinsame Teiler von (a) und (b). Es sollte klar sein, dass (gcd(a,b)) positiv sein muss.

Beispiel (PageIndex{1}label{zB:gcd-01})

Die gemeinsamen Teiler von 24 und 42 sind (pm1), (pm2), (pm3) und (pm6). Unter ihnen ist 6 die größte. Daher (gcd(24,42)=6). Die gemeinsamen Teiler von 12 und 32 sind (pm1), (pm2) und (pm4), daraus folgt (gcd(12,32)=4).

praktische Übung (PageIndex{1}label{he:gcd-01})

Überprüfen Sie, dass [gcd(5,35)=5, quadgcd(-5,10)=5, quadgcd(20,-10)=10, quadmbox{und}quad gcd(20,70)=10. onumber] Erkläre, warum (gcd(3,5)=1)

Beispiel (PageIndex{2}label{zB:gcd-02})

Können Sie erklären, warum (gcd(0,3)=3)? Wie wäre es mit (gcd(0,-3)=3)?

Lösung

Denken Sie daran, dass 0 durch jede ganze Zahl ungleich null teilbar ist. Daher sind alle Teiler von 3 auch Teiler von 0. Offensichtlich ist 3 selbst der größte Teiler von 3. Daher gilt (gcd(0,3)=3).

praktische Übung (PageIndex{2}label{he:gcd-02})

Erklären Sie, warum (gcd(0,-8)=8).

Satz (PageIndex{1}label{thm:gcd0b})

Für jede von Null verschiedene ganze Zahl (b) gilt (gcd(0,b)=|b|).

Beweis

Der größte positive Teiler von (b) ist (|b|). Da (|b|) auch 0 teilt, schließen wir, dass (gcd(0,b)=|b|).

Satz 5.4.1 sagt uns, dass (gcd(0,b)=|b|) falls (b) ungleich Null ist. Aus der Definition des gemeinsamen Teilers und des größten gemeinsamen Teilers ist klar, dass (gcd(a,b) = gcd(b,a)) und (gcd(a,b) = gcd( pm a,pm b)). Wir können also (1leq aleq b) annehmen.

Satz (PageIndex{2})

Seien (a) und (b) ganze Zahlen mit (1leq aleq b). Wenn (b=aq+r), wobei (0leq r< a), dann (gcd(b,a)=gcd(a,r)).

Beweis

Um unsere Argumentation zu erleichtern, seien (d=gcd(b,a)) und (e=gcd(a,r)). Definitionsgemäß ist (d) ein Teiler von (b) und (a). Daher gilt (b=dx) und (a=dy) für einige ganze Zahlen (x) und (y). Dann ist [r = b-aq = dx-dycdot q = d(x-yq), onumber] wobei (x-yq) eine ganze Zahl ist. Daher (dmid r). Dies macht (d) zu einem gemeinsamen Teiler von (r) und (a). Da (e) der größte gemeinsame Teiler von (a) und (r) ist, bestimmen wir (dleq e).

Ebenso ist (e=gcd(a,r)) ein Teiler von (a) und (r). Also (a=eu) und (r=ev) für einige ganze Zahlen (u) und (v). Dann ist [b = aq+r = acdot eu+ev = e(au+v), onumber] wobei (au+v) eine ganze Zahl ist. Daher (emid b). Dies macht (e) zu einem gemeinsamen Teiler von (b) und (a). Da (d) der größte gemeinsame Teiler von (b) und (a) ist, folgern wir (eleq d). Zusammen mit (dleq e) schließen wir (d=e).

Beispiel (PageIndex{3}label{zB:gcd-03})

Aus (997=996cdot1+1) erhalten wir (gcd(997,996)=gcd(996,1)=1).

Der Satz stellt sicher, dass (gcd(b,a) = gcd(a,r)). Wir können den Satz wieder auf (gcd(a,r)) anwenden. Die Division von (a) durch (r) erzeugt einen neuen Quotienten und einen neuen Rest. Wiederholen Sie ggf. den Vorgang, bis der Rest Null wird. Wenn wir (b=r_0) und (a=r_1) bezeichnen, dann ist [egin{array}{[email protected]{qquadqquad}l} r_0 &=& r_1 q_1 + r_2, & 0 leq r_2 < r_1, r_1 &=& r_2 q_2 + r_3, & 0leq r_3 < r_2, r_2 &=& r_3 q_3 + r_4, & 0leq r_4 < r_3, vdots & & vdots r_{k-1} &=& r_k q_k + r_{k+1}, & 0leq r_{k+1} < r_k, vdots & & vdots r_{n-3 } &=& r_{n-2} q_{n-2} + r_{n-1}, & 0leq r_{n-1} < r_{n-2}, r_{n-2} &=& r_{n-1} q_{n-1} + r_n, & r_n=0. end{array} onumber] Daraus folgt [gcd(b,a) = gcd(r_0,r_1) = gcd(r_1,r_2) = cdots = gcd(r_{n-1} ,r_n) = gcd(r_{n-1},0) = r_{n-1}. keine Nummer] Der letzte von Null verschiedene Rest ist (gcd(a,b)). Diese Methode zum Finden des größten gemeinsamen Teilers heißt Euklidischer Algorithmus.

Beispiel (PageIndex{4}label{zB:gcd-04})

Finden Sie (gcd(426,246)).

Lösung

Durch wiederholtes Anwenden des Satzes finden wir [egin{array}{[email protected]{qquadqquad}lcl} 426 &=& 246cdot1+180, & gcd(426,246) &=& gcd(246,180) 246 &=& 180cdot1+ 66, & gcd(246,180) &=& gcd(180, 66) 180 &=& 66cdot2+ 48, & gcd(180, 66) &=& gcd( 66, 48) 66 &=& 48cdot1+ 18, & gcd( 66, 48) &=& gcd( 48, 18) 48 &=& 18cdot2+ 12, & gcd( 48, 18) &=& gcd( 18, 12) 18 &=& 12cdot1+ 6, & gcd( 18, 12) &=& gcd( 12, 6) 12 &=& 6 cdot2+ 0, & gcd( 12, 6) &=& gcd( 6, 0) = 6. end{array} onumber] Daher (gcd(426,246)=6).

praktische Übung (PageIndex{3}label{he:gcd-03})

Bestimme (gcd(732,153)).

praktische Übung (PageIndex{4}label{he:gcd-04})

Bestimme (gcd(6958,2478)).

Von Hand ist es effizienter, ein zweispaltiges Format zu verwenden. Tragen Sie zuerst die beiden Zahlen 426 und 246 in zwei separate Spalten ein, wobei die größere Zahl links steht. Führe eine kurze Division durch und schreibe den Quotienten links: [egin{array}{r|r|r|r} 1 & 426 & 246 & & 246 & & cline{2-2 } & 180 & & end{array} onumber]

Führen Sie in der nächsten Runde eine weitere kurze Division auf den beiden Zahlen 246 und 180 unten durch. Da die größere Zahl jetzt in der rechten Spalte steht, lassen Sie den Quotienten rechts davon:

[egin{array}[t]{r|r|r|r} 1 & 426 & 246 & 1 & 246 & 180 & hline & 180 & 66 & end{array} onumber ]

Fahren Sie auf diese Weise fort, bis der Rest 0 wird. Der letzte von Null verschiedene Eintrag am unteren Rand ist der größte gemeinsame Teiler. Wir können auch alle Quotienten links lassen:

[egin{array}[c]{r|r|r|r} 1 & 426 & 246 & 1 & 246 & 180 & hline 2 & 180 & 66 & 1 & 132 & 48 & hline 2 & 48 & 18 & 1 & 36 & 12 & hline 2 & 12 & 6 & & 12 & & hline & 0 & end{array} hskip0. 5inmbox{or}hskip0.5in egin{array}[c]{r|r|r|r} 1 & 426 & 246 & 1 & 246 & 180 & hline 2 & 180 & 66 & 1 & 132 & 48 & hline 2 & 48 & 18 & 1 & 36 & 12 & hline 2 & 12 & 6 & & 12 & & hline & 0 & end{array} onumber]

praktische Übung (PageIndex{5}label{he:gcd-05})

Verwenden Sie das zweispaltige Format, um (gcd(153,732)) zu berechnen.

praktische Übung (PageIndex{6}label{zB:gcd-06})

Verwenden Sie das zweispaltige Format, um (gcd(6958,2478)) zu berechnen.

Bei gegebenen ganzen Zahlen (m) und (n) heißen die Zahlen der Form (ms+nt), wobei (s,t) ganze Zahlen sind, die Linearkombinationen von (m) und (n). Sie spielen eine wichtige Rolle beim Studium von (gcd(m,n)), wie der nächste Satz zeigt.

Satz (PageIndex{3})

Für beliebige ganze Zahlen (a) und (b) gibt es ganze Zahlen (s) und (t) mit (gcd(a,b)=as+bt).

Beweis

Der Beweis dieses Satzes ist langwierig und kompliziert. Wir überlassen es zusammen mit anderen verwandten Ergebnissen, von denen viele eher technisch sind, dem nächsten Abschnitt.

Satz (PageIndex{4})

Jede Linearkombination von (a) und (b) ist ein Vielfaches von (gcd(a,b)).

Folgerung (PageIndex{5})

Der größte gemeinsame Teiler zweier von Null verschiedenen ganzen Zahlen (a) und (b) ist die kleinste positive ganze Zahl unter all ihren Linearkombinationen.

Es ist wichtig zu verstehen, was diese drei Ergebnisse aussagen. Wenn wir eine Linearkombination von (a) und (b) finden, erhalten wir nur ein Vielfaches von (gcd(a,b)). Nur eine spezielle Linearkombination ergibt den exakten Wert von (gcd(a,b)).

Beispiel (PageIndex{5}label{zB:gcd-05})

Seien (n) und (n+1) zwei aufeinanderfolgende positive ganze Zahlen. Dann impliziert [ncdot(-1)+(n+1)cdot1 = 1 onumber], dass 1 ein Vielfaches des größten gemeinsamen Teilers von (n) und (n+1) ist. Dies bedeutet, dass der größte gemeinsame Teiler 1 sein muss. Daher gilt (gcd(n,n+1)=1) für alle ganzen Zahlen (n).

Definition

Zwei ganze Zahlen (a) und (b) heißen relativ prim wenn (gcd(a,b)=1). Daher sind (a) und (b) relativ prim, wenn sie außer (pm 1) keine gemeinsamen Teiler haben.

Beispiel (PageIndex{6}label{zB:gcd-06})

Beweisen Sie, dass, wenn (gcd(a,b)=1), dann (gcd(a+b,a-b)) gleich 1 oder 2 ist.

Lösung

Aus den Linearkombinationen [egin{aligned} (a+b)cdot1+(ab)cdot1 &=& 2a, (a+b)cdot1+(ab)cdot(-1) &=& 2b , end{aligned} onumber] wissen wir, dass (gcd(a+b,ab)) sowohl (2a) als auch (2b) teilt. Da (gcd(a,b)=1), folgern wir, dass (gcd(a+b,ab)) 2 teilt. Folglich ist (gcd(a+b,ab))) entweder 1 oder 2.

Beispiel (PageIndex{7}label{zB:gcd-07})

Zeigen Sie, dass, wenn (gcd(a,b)=1), dann (gcd(2a+b,a+2b)) entweder gleich 1 oder 3 ist.

Lösung

Aus den Linearkombinationen [egin{aligned} (2a+b)cdot 2 +(a+2b)cdot(-1) &=& 3a, (2a+b)cdot(-1)+ (a+2b)cdot 2 &=& 3b, end{aligned} onumber] wir wissen, dass (gcd(2a+b,a+2b)) sowohl (3a) als auch ( 3b). Da (gcd(a,b)=1), schließen wir, dass (gcd(2a+b,a+2b)) 3 teilt. Somit gilt (gcd(a+b,ab) ) ist 1 oder 3.

praktische Übung (PageIndex{7}label{he:gcd-07})

Was sind die möglichen Werte von (gcd(5m+7n,7m+5n)), wenn die beiden positiven ganzen Zahlen (m) und (n) teilerfremd sind?

Beispiel (PageIndex{8}label{zB:gcd-08})

Finden Sie die ganzen Zahlen (s) und (t) mit (6=gcd(426,246)=246s+426t).

Lösung

Zuvor haben wir untersucht, wie man (gcd(426,246)=6) findet. Bei jeder Division wollen wir den Rest als Linearkombination von 246 und 426 ausdrücken. So läuft die Berechnung ab:

[egin{array}{lrcl} 426 = 246cdot1+180,& 180 &=& 246cdot(-1)+426cdot1 [3pt] 246 = 180cdot1+66, & 66 & =& 246cdot1+180cdot(-1) & &=& 246cdot1+[246cdot(-1)+426cdot1]cdot(-1) & &=& 246cdot2 +426cdot(-1) [3pt] 180 = 66cdot2+48, & 48 &=& 180cdot1+66cdot(-2) & &=& [246cdot(-1 )+426cdot1]cdot1 +[246cdot2+426cdot(-1)]cdot(-2) & &=& 246(-5)+426cdot3 66 = 48cdot1 +18, & 18 &=& 66cdot1+48cdot(-1) & &=& [246cdot2+426cdot(-1)]cdot1 + [246(-5)+426 cdot3]cdot(-1) & &=& 246cdot7+426cdot(-4) [3pt] 48 = 18cdot2+12, & 12 &=& 48cdot1+18cdot (-2) & &=& [246(-5)+426cdot3]cdot1 + [246cdot7+426cdot(-4)]cdot(-2) & &=& 246 cdot(-19)+426cdot11 [3pt] 18 = 12cdot1+6, & 6 &=& 18cdot1 + 12cdot(-1) & &=& [246cdot7+ 426cdot(-4)]cdot1 + [246cdot(-19)+426cdot11]cdot(-1) & &=& 246cdot26+426cdot(-15) end{ Array} onumber]

Die Antwort lautet (6=246cdot26+426cdot(-15)).

Die Berechnung ist mühsam! Das erweiterter euklidischer Algorithmus sorgt für Entlastung. Es verfolgt zwei Folgen von ganzen Zahlen (s_k) und (t_k) neben (r_k), so dass [r_k = a s_k + b t_k. onumber] Dies drückt jeden Rest als Linearkombination von (a) und (b) aus. Da der letzte von Null verschiedene Rest (gcd(a,b)) ist, ist die entsprechende Linearkombination die gesuchte Antwort.

Die Werte von (s_k) und (t_k) für das letzte Beispiel sind unten zusammengefasst:

[egin{array}{|c|r|r|r| } hline k & r_k & s_k & t_k hline 2 & 180 & -1 & 1 3 & 60 & 2 & -1 4 & 48 & -5 & 3 5 & 18 & 7 & -4 6 & 12 & -19 & 11 7 & 6 & 26 & -15 hline end{array} onumber]

Die Hauptfrage ist: Wie können wir diese Werte effizient berechnen?

Die obige Tabelle beginnt mit (k=2). Wie wäre es mit (k=0) und (k=1)? Aus [b = r_0 = a s_0 + b t_0, onumber] bestimmen wir (s_0=0) und (t_0=1). Ähnlich,

[a = r_1 = a s_1 + b t_1 onumber]

impliziert, dass (s_1=1) und (t_1=0) sind. Daher beginnt die Liste der Werte von (s_k) und (t_k) mit folgendem:

[egin{array}{ccc} k & s_k & t_k 0 & 0 & 1 1 & 1 & 0 end{array} onumber]

Im Allgemeinen sollten wir, bevor wir die Division (r_{k-1}div r_k) ausführen, bereits (s_0) durch (s_k) und (t_0) durch (t_k ). Nach der Division erhalten wir (q_k) und (r_{k+1}) wie in

[r_{k-1} = r_k q_k + r_{k+1}. keine Nummer]

Als nächstes berechnen wir (s_{k+1}) und (t_{k+1}), bevor wir zur nächsten Division übergehen. Wir finden

[egin{array}{rcl} r_{k+1} &=& r_{k-1} - r_k q_k &=& (a s_{k-1} + bt_{k-1}) - (a s_k + b t_k) q_k &=& a (s_{k-1} – s_k q_k) + b (t_{k-1} – t_k q_k). end{array} onumber]

Daher brauchen wir

[egin{array}{r c l} s_{k+1} &=& s_{k-1} - s_k q_k, t_{k+1} &=& t_{k-1} - t_k q_k. end{array} onumber]

In Worten:

[displaylines{ mbox{nächster $s$-Wert} = mbox{vorheriger-vorheriger $s$-Wert} - mbox{vorheriger $s$-Wert} imes mbox{entsprechender $q$}, cr mbox{nächster $t$-Wert} = mbox{vorheriger-vorheriger $t$-Wert} - mbox{vorheriger $t$-Wert} imes mbox{entsprechender $q$}. cr} onumber]

Angenommen, zu einem bestimmten Zeitpunkt sind die Werte von (s), (t) und (q) wie folgt:

[egin{array}{ccc} k & s_k & t_k & q_k ​​ 0 & 0 & 1 & 1 & 1 & 0 & 1 2 & -1 & 1 & 1 3 & 2 & -1 & 2 & & & 1 & & & 2 & & & 1 & & & 2 end{array} onumber] Dann [displaylines{ mbox{next $s$ -value} = -1-2cdot2 = -5, cr mbox{next $t$-value} = 1-(-1)cdot2 = 3. cr} onumber] Nun wird die Liste zu [egin{array}{ccc} k & s_k & t_k & q_k ​​ 0 & 0 & 1 & 1 & 1 & 0 & 1 2 & -1 & 1 & 1 3 & 2 & - 1 & 2 4 & -5 & 3 & 1 & & & 2 & & & 1 & & & 2 end{array} onumber]

Die gesamte Berechnung kann in einem modifizierten zweispaltigen Format durchgeführt werden.

Beispiel (PageIndex{9}label{zB:gcd-09})

Finden Sie ganze Zahlen (s) und (t) mit (gcd(246.426)=246s+426t).

Lösung

Kopieren Sie zunächst die Quotienten aus der Spalte ganz rechts und fügen Sie sie zwischen diesen Quotienten in der Spalte ganz links ein:

[egin{array}[c]{r|r|r|r} 1 & 426 & 246 & 1 & 246 & 180 & cline{2-3} 2 & 180 & 66 & 1 & 132 & 48 & cline{2-3} 2 & 48 & 18 & 1 & 36 & 12 & cline{2-3} 2 & 12 & 6 & & 12 & & cline{2-2} & 0 & end{array} qquadmbox{wird}qquad egin{array}[c]{r|r|r|r} 1 & 426 & 246 & 1 1 & 246 & 180 & Kline{2-3} 2 & 180 & 66 & 1 1 & 132 & 48 & Kline{2-3} 2 & 48 & 18 & 1 1 & 36 & 12 & cline{2-3} 2 & 12 & 6 & & 12 & & cline{2-2} & 0 & end{array} onumber]

Berechnen Sie als nächstes (s_k) und (t_k) neben diesen Quotienten (wir müssen die Werte von (k) nicht aufzeichnen):

[egin{array}[t]{[email protected]{qquad}r|r|r|r} s_k & t_k & multicolumn{1}{r}{q_k} 0 & 1 1 & 0 & 1 & 426 & 246 & 1 -1 & 1 & 1 & 246 & 180 & cline{4-5} 2 & -1 & 2 & 180 & 66 & 1 -5 & 3 & 1 & 132 & 48 & cline{4-5} 7 & -4 & 2 & 48 & 18 & 1 -19 & 11 & 1 & 36 & 12 & cline{4-5} 26 & -15 & 2 & 12 & 6 & & & & 12 & & cline{4-4} & & & 0 & end{array} onumber] Der letzte von Null verschiedene Rest ist der größte gemeinsame Teiler, und die letzte Linearkombination liefert die gewünschte Antwort. Wir finden (gcd(246.426) = 6 = 26cdot246-15cdot426).

Beachten Sie, dass sich, beginnend mit (k=2), die Vorzeichen von (s_k) und (t_k) abwechseln. Dies ermöglicht eine schnelle Überprüfung ihrer Zeichen. Außerdem sind die Vorzeichen von (s_k) und (t_k) für jedes (kgeq2) entgegengesetzt.

praktische Übung (PageIndex{8}label{he:gcd-08})

Verwenden Sie das zweispaltige Format, um die Linearkombination zu finden, die (gcd(153,732)) ergibt.

praktische Übung (PageIndex{9}label{he:gcd-09})

Verwenden Sie das zweispaltige Format, um die Linearkombination zu finden, die (gcd(2478,6958)) ergibt.

Zusammenfassung und Rückblick

  • Der größte gemeinsame Teiler von zwei ganzen Zahlen, nicht beide Null, ist die größte (daher muss sie positiv sein) ganze Zahl, die beide teilt.
  • Verwenden Sie den euklidischen Algorithmus, um den größten gemeinsamen Teiler zu finden. Es kann in einem zweispaltigen Format implementiert werden.
  • Unter Verwendung einer erweiterten Version mit zwei zusätzlichen Spalten zur Berechnung von (s_k) und (t_k) können wir die spezielle Linearkombination zweier ganzer Zahlen finden, die ihren größten gemeinsamen Teiler ergibt.
  • Im Allgemeinen ergibt eine Linearkombination zweier ganzer Zahlen nur ein Vielfaches ihres größten gemeinsamen Teilers.

Übung (PageIndex{1}label{ex:gcd-01})

Finden Sie für jedes der folgenden Paare von ganzen Zahlen die Linearkombination, die ihrem größten gemeinsamen Teiler entspricht.

  1. 27, 81
  2. 24, 84
  3. 1380, 3020

Übung (PageIndex{2}label{ex:gcd-02})

Finden Sie für jedes der folgenden Paare von ganzen Zahlen die Linearkombination, die ihrem größten gemeinsamen Teiler entspricht.

  1. 120, 615
  2. 412, 936
  3. 1122, 3672

Übung (PageIndex{3}label{ex:gcd-03})

Was sind die möglichen Werte von (gcd(2a+5b,5a-2b)), wenn die beiden positiven ganzen Zahlen aa und bb teilerfremd sind?

Übung (PageIndex{4}label{ex:gcd-04})

Beweisen Sie, dass alle aufeinander folgenden ungeraden positiven ganzen Zahlen relativ prim sind.

Übung (PageIndex{5}label{ex:gcd-05})

Seien (m) und (n) positive ganze Zahlen. Beweisen Sie, dass (gcd(m,m+n)mid n).

Übung (PageIndex{6}label{ex:gcd-06})

Seien (a) und (b) ganze Zahlen mit (1

Übung (PageIndex{7}label{ex:gcd-07})

Was sind die möglichen Werte von (gcd(3m-5n,5m+3n)), wenn die beiden positiven ganzen Zahlen (m) und (n) teilerfremd sind?

Übung (PageIndex{8}label{ex:gcd-08})

Was sind die möglichen Werte von (gcd(4p+7q,7p-4q)), wenn die beiden positiven ganzen Zahlen (p) und (q) teilerfremd sind?


5.4: Größte gemeinsame Teiler - Mathematik

Wie wir gesehen haben, müssen wir, um zu entscheiden, ob ein Divisionsproblem gelöst werden kann, herausfinden, ob der größte gemeinsame Teiler der Zahl, durch die wir dividieren, und der Modulus 1 ist. Der größte gemeinsame Teiler von zwei Zahlen heißt im Allgemeinen der größte gemeinsame Teiler der beiden Zahlen. Das Auffinden des größten gemeinsamen Teilers kleiner Zahlen ist durch Inspektion leicht zu bewerkstelligen. Betrachten Sie alle Teiler einer Zahl und sehen Sie, ob sie die andere Zahl teilen oder nicht, und wählen Sie den größten Teiler aus, der dies tut. Bei großen Zahlen kann dies jedoch viel Zeit in Anspruch nehmen. Sie würden wahrscheinlich eine ganze Weile suchen, bevor Sie herausfinden, dass der größte gemeinsame Teiler von 378 und 3465 63 ist. Glücklicherweise gibt es eine Methode, um den größten gemeinsamen Teiler von zwei ganzen Zahlen zu finden, die kein Erraten erfordert. Die Methode ist sehr alt und wird Euklidischer Algorithmus genannt. Es ist nach dem griechischen Mathematiker Euklid benannt, der um 200 v. Chr. lebte. Euklid ist vor allem für seine Arbeiten in Geometrie bekannt, aber er hat auch viel mit Zahlen gearbeitet. Das Wort "Algorithmus" ist nur eine ausgefallene Art, Methode zu sagen. Der euklidische Algorithmus ist also nur die Methode von Euklid, um die größten gemeinsamen Teiler zu finden.

Um diese Methode zu beschreiben, erinnern wir uns an die Begriffe, die wir verwenden, wenn wir eine Divisionsaufgabe (in gewöhnlicher Arithmetik) lösen. Eine Zahl (der Dividenden) ergibt, wenn sie durch eine zweite Zahl (den Divisor) geteilt wird, eine ganzzahlige Antwort (den Quotienten) plus einen Bruchteil (den Rest/den Divisor): Bei der Division 25/7 haben wir also: und 25 ist den Dividenden, 7 den Divisor, 3 den Quotienten und 4 den Rest. Euklids Methode beinhaltet nun eine Reihe von Divisionen. Um den größten gemeinsamen Teiler zweier Zahlen zu finden, dividiere zuerst die größere durch die kleinere und schreibe das Problem wie oben. Die nächste Division ist diejenige, die Sie erhalten, indem Sie den Bruchteil der letzten Division "umdrehen" - das heißt, der neue Dividenden ist der alte Teiler und der neue Teiler ist der alte Rest. Wenn dies erledigt ist, wiederholen Sie den Vorgang (d. h. drehen Sie den neuen Bruchteil um, um die nächste Division zu erhalten). Tun Sie dies, bis Sie aufhören müssen, weil ein Rest zu 0 wird. Der letzte Rest ungleich Null ist der größte gemeinsame Teiler der beiden ursprünglichen Zahlen. Verwenden wir diese Methode zum Beispiel, um den größten gemeinsamen Teiler von 7 und 25 zu finden (was wir leicht erkennen können, ist 1 ). Der erste Schritt wurde oben gemacht. Die nächste Division ist 7/4 (das Umdrehen von 4/7). Dies ergibt 7/4 = 1 + 3/4. Als nächstes machen wir 4/3 = 1 + 1 /3. Als nächstes machen wir 3/1 = 3 + 0, also hören wir hier auf. Der letzte Rest ungleich Null ist die fette 1 des vorletzten Schrittes, und dies ist der größte gemeinsame Teiler. Was für eine Menge Arbeit, um eine Antwort zu bekommen, die wir von Anfang an wussten! Vielleicht wird Sie dieses nächste Beispiel davon überzeugen, dass sich die Mühe lohnen könnte. Verwenden wir die Methode von Euklid, um den größten gemeinsamen Teiler von 378 und 3465 zu finden.

3465/378 = 9 + 63 /378
378/63 = 6 + 0.
Der größte gemeinsame Teiler ist also 63. Das war einfach!

Verwenden Sie die Methode von Euklid, um den größten gemeinsamen Teiler dieser Zahlenpaare zu finden.

Zu dieser Methode müssen wir zwei Dinge sagen. Wenn im ersten Schritt kein Rest vorhanden ist, ist der größte gemeinsame Teiler die kleinere der beiden Zahlen. Die zweite Sache ist zu beachten, dass die Quotienten, die in jedem Divisionsschritt erhalten werden, keine Rolle spielen, um den größten gemeinsamen Teiler zu finden. aber ignorieren Sie sie nicht, wir werden sie später verwenden.

Wenn wir versuchen, eine arithmetische Uhrendivision durchzuführen, wie zum Beispiel (5 ÷ 7) mod 25 zu finden, tun wir dies in zwei Schritten, da (5 ÷ 7) mod 25 = 5 × (1 ÷ 7) mod 25 ist. Das bedeutet, dass wir kann zuerst den Wert von (1 & dividiere 7) mod 25 finden und dann einfach mit 5 multiplizieren (mod 25). In diesem Beispiel ist (5 ÷ 7) mod 25 die Antwort auf die Frage 7 × ? = 5 mod 25. Wenn wir wüssten, dass (1 ÷ 7) mod 25 = 18, dann erhalten wir die Antwort auf unsere Frage, indem wir 5 &mal 18 mod 25 = 90 mod 25 = 15 berechnen. Beachten Sie, dass 7 &mal 15 mod 25 = 105 mod 25 = 5, also ist 15 die richtige Antwort auf unser Divisionsproblem. Das bedeutet, dass wir immer dann, wenn wir eine uhrarithmetische Division durchführen, die Division immer mit Dividende 1 statt mit dem tatsächlichen Dividenden durchführen und dann mit dem realen Dividenden des Problems multiplizieren können. Wie wir sehen werden, funktioniert unsere Methode für diese Aufteilungen nur, wenn wir unsere Aufteilungsaufgaben auf diese Weise lösen.

Verwenden Sie die gegebenen Informationen, um die Antworten auf diese Aufteilungsprobleme zu finden.

  1. (6 ÷ 9) mod 17, wenn Sie wissen, dass (1 ÷ 9) mod 17 = 2.
  2. (12 ÷ 5) mod 24, wenn Sie wissen, dass (1 ÷ 5) mod 24 = 5.
  3. (8 ÷ 6) mod 35, wenn Sie wissen, dass (1 ÷ 6) mod 35 = 6.
  • 17/9 = 1 + 8/9.
  • 9/8 = 1 + 1 /8.
  • 8/1 = 8 + 0.
  • 17 = 1 &mal 9 + 8, also 8 = 17 - 1 &mal 9.
  • 9 = 1 &mal 8 + 1, also 1 = 9 - 1 &mal 8.
  • 25/7 = 3 + 4/7 ===> 4 = 25 - 3 &mal 7
  • 7/4 = 1 + 3/4 ===> 3 = 7 - 1 &mal 4
  • 4/3 = 1 + 1/3 ===> 1 = 4 - 1 &mal 3
  • 3/1 = 3 + 0

Verwenden Sie diese Methode, um die Antworten auf diese Aufteilungsprobleme zu finden.

  • 21/9 = 2 + 3/9 ===> 3 = 21 - 2 &mal 9
  • 9/3 = 3 + 0
  • 25/9 = 2 + 7/9 ===> 7 = 25 - 2 &mal 9
  • 9/7 = 1 + 2/7 ===> 2 = 9 - 1 &mal 7
  • 7/2 = 3 + 1/2 ===> 1 = 7 - 3 &mal 2

Verwenden Sie diese Methode, um die Antworten auf diese Aufteilungsprobleme zu finden.

  1. (2 &dividieren 3) mod 5 =
  2. (5 &dividieren 3) mod 6 =
  3. (2 &dividiere 5) mod 6 =
  4. (13 & dividiere 6) mod 18 =
  5. (12 & dividiere 7) mod 25 =

Im nächsten Abschnitt werden wir sehen, wie wir die Taktarithmetik (einschließlich Division) verwenden können, um geheime Nachrichten zu erstellen. Antworten auf die Fragen zu den größten gemeinsamen Teilern

  1. 1 102/25 = 4 + 2/25 25/2 = 12 + 1 /2 2/1 = 2 + 0.
  2. 9 243/198 = 1 + 45/198 198/45 = 4 + 18/45 45/18 = 2 + 9 /18 18/9 = 2 + 0.
  3. 77 7469/2464 = 3 + 77 /2464 2464/77 = 32 + 0.
  4. 1 4999/1109 = 4 + 563/1109 1109/563 = 1 + 546/563 563/546 = 1 + 17/546 546/17 = 32 + 2/17 17/2 = 8 + 1 /2 2/1 = 2 + 0.
  1. 12 seit 6 &mal 2 mod 17 = 12. Check : 9 &mal 12 mod 17 = 108 mod 17 = 6.
  2. 12 seit 12 &mal 5 mod 24 = 60 mod 24 = 12. Check : 5 &mal 12 mod 24 = 60 mod 24 = 12.
  3. 13 seit 8 &mal 6 mod 35 = 48 mod 35 = 13. Check : 6 &mal 13 mod 35 = 78 mod 35 = 8.

    2
    17/9 = 1 + 8/9 ===> 8 = 17 - (1 &mal 9)
    9/8 = 1 + 1/8 ===> 1 = 9 - (1 &mal 8)
    1 = 9 - (1 &mal (17 - (1 &mal 9))) = 9 -17 + 9 = 9 &mal 2 - 17 &mal 1.

    4
    5/3 = 1 + 2/3 ===> 2 = 5 - (1 &mal 3)
    3/2 = 1 + 1/2 ===> 1 = 3 - (1 &mal 2)
    1 = 3 - (1 &mal (5 - (1 &mal 3))) = 3 -5 + 3 = 3 &mal 2 - 5 &mal 1.
    Also (1 ÷ 3) mod 5 = 2 und daher (2 ÷ 3) mod 5 = 2 &mal 2 mod 5 = 4.


Über den Autor

DONALD BINDNER, PhD, ist Assistant Professor am Department of Mathematics and Computer Science der Truman State University.

MARTIN J. ERICKSON, PhD, ist Professor für Mathematik am Department of Computer Science der Truman State University und Autor bzw. Co-Autor zahlreicher Bücher zu mathematischen Themen.

JOE HEMMETER, PhD, ist freiberuflicher Softwareentwickler und ehemaliger Professor für Mathematik an der University of Delaware und der Truman State University.


Blog Archiv

Fraktionen sind Freunde von allen, oder zumindest können sie es sein. Sie sehen vielleicht ein wenig beängstigend aus, sind es aber nicht wirklich. Brüche sind ansonsten als Dezimalzahlen bekannt. Brüche (und Dezimalzahlen) stellen die Leerzeichen zwischen den ganzen Zahlen (oder Zählzahlen) auf der Zahlengeraden dar. Ganzzahlen sind beispielsweise die Menge negativer Zahlen, positiver Zahlen und Null (…-2, -1, 0, 1, 2…) Brüche (und Dezimalzahlen sind die Werte zwischen diesen Zahlen (wie 1,5 oder -1,5 .). ).

Brüche (und Dezimalstellen) stellen Teilbeträge dar. Ich habs?

Brüche haben zwei Zahlen mit einem Strich dazwischen. Die obere Zahl heißt Zähler, die untere Zahl Nenner. Die Trennlinie bedeutet “divided by”. Brüche stellen also dar, dass ein Betrag durch einen anderen Betrag geteilt wird.

Nehmen Sie zum Beispiel 1/2. Das bedeutet eins geteilt durch zwei.

Für ein anderes Beispiel nehmen Sie 5/7. Das bedeutet fünf geteilt durch sieben.

Manche Leute sagen, “Sie können das nicht tun, weil die erste Zahl kleiner ist als die zweite,”, aber ja, das können Sie. Sie fügen einen Dezimalpunkt und einige Nullen hinzu und beginnen wie gewohnt zu dividieren. Dann erhalten Sie eine Dezimalzahl als Antwort.

Nur wenn der Zähler größer als der Nenner ist, erhalten Sie am Ende einen Betrag, der größer als eins ist.

Um mit Brüchen gut zurechtzukommen, müssen Sie nur die Regeln für alle vier Operationen lernen. Bereit?

Addieren und Subtrahieren: Brüche müssen einen gemeinsamen Nenner haben. Wenn dies nicht der Fall ist, müssen Sie das kleinste gemeinsame Vielfache (LCM) finden und es zum kleinsten gemeinsamen Nenner (LCD) machen. Wandeln Sie Brüche mit LCD in äquivalente Brüche um, indem Sie Zähler und Nenner mit derselben Zahl multiplizieren. Dann addieren oder subtrahieren Sie einfach die Zähler (die Nenner bleiben gleich).

4 ist die LCM von 4 und 2, also kann der zweite Bruch gleich bleiben, aber wir müssen den ersten Bruch mit 2/2 multiplizieren, um einen äquivalenten Bruch zu erhalten (1/2 * 2/2 = 2/4)

Jetzt können wir addieren: 2/4 + 3/4 = 5/4 (das ist ein unechter Bruch, da der Zähler größer als der Nenner ist, also möchten wir ihn durch Division 5/4 = 1 und 1/4 . reduzieren reduce

Multiplizieren: Zähler mit Zähler und Nenner mit Nenner multiplizieren

Zum Beispiel 1/2 * 3/4 ​​= 3/8 EINFACH!

Teilen: Multipliziere den Kehrwert (die Umkehrung des zweiten Bruchs – drehe ihn auf den Kopf – Ich nenne das “keep, change, flip” weil du den ersten Bruch behältst, dividiere in Multiplikation und drehe den zweiten Bruch .

Zum Beispiel 1/2 geteilt durch 3/4

1/2 *4/3 = 4/6 (was sich zu 2/3 vereinfacht)

Kapiert? Sehen Sie, ich habe Ihnen gesagt, es ist nicht so schlimm.

Deutsch: Display mit Brüchen. (Bildnachweis: Wikipedia)

Alle Brüche müssen in einfachster Form ausgedrückt werden. Das bedeutet, dass Zähler und Nenner durch ihren größten gemeinsamen Faktor (GCF) dividiert werden. In der letzten Aufgabe sind sowohl 4 als auch 6 durch 2 teilbar. Also vereinfachten wir 4/6, indem wir durch 2/2 dividierten, und erhielten 2/3. Es gibt keinen anderen Faktor als 1 durch den wir sowohl 2 als auch 3 dividieren können, also sagen wir, dass es in der einfachsten Form ist.

Im Additionsbeispiel haben wir einen unechten Bruch erhalten, also haben wir 5 durch 4 geteilt. Aus 4 wird einmal 5 mit einem Rest von 1, also nennen wir es 1 und 1/4. Das wird als gemischte Zahl bezeichnet, weil es sowohl eine ganze Zahl (1) als auch eine Bruchzahl (1/4) hat. Es ist gemischt.

Um den umgekehrten Weg von einer gemischten Zahl zu einer unechten Zahl zu gehen (was Sie tun müssen, wenn Sie alle vier Operationen mit gemischten Zahlen ausführen), müssen Sie nur den Nenner mit der ganzen Zahl multiplizieren und dann den Zähler addieren. Dann drücken Sie diesen Betrag im Zähler aus und behalten den gleichen Nenner bei.

Zum Beispiel 1 und 1/4. Multiplizieren Sie 4*1 und addieren Sie dann 1. Das Ergebnis ist 5/4.

Vergessen Sie nicht den Unterschied zwischen a Faktor (zur Vereinfachung verwendet) und a mehrere (wird beim Addieren und Subtrahieren verwendet). Ein Faktor zeigt eine Division an und ein Vielfaches zeigt eine Multiplikation an.


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))


Darstellung von Zahlen durch zerlegbare Formen

Definition.

Die binäre quadratische Form f(x, y) = Axt 2 + Bxy + Cy 2 mit rationalen ganzzahligen Koeffizienten heißt Primitive wenn der größte gemeinsame Teiler der Koeffizienten 1 ist. Die ganze Zahl B 2 – 4AC heißt der diskriminierend der primitiven Form f.

Die Diskriminante einer primitiven Form unterscheidet sich daher von ihrer Determinante AC – (B 2/4) um den Faktor -4.

Es ist leicht zu erkennen, dass jede Form, die einer primitiven Form entspricht, auch primitiv ist. Unter einer linearen Änderung von Variablen mit Matrix C die Determinante einer quadratischen Form wird mit (det C) 2 und ändert sich daher nicht, wenn det C = ± 1. Daher haben äquivalente primitive Formen die gleiche Diskriminante.


Größte gemeinsame Faktoren

Der größte gemeinsame Faktor (G.C.F.) von zwei Zahlen ist die größte Zahl, die ein Teiler von beiden ist. Es wird manchmal als der größte gemeinsame Teiler bezeichnet. Es kann verwendet werden, um Brüche zu vereinfachen (oder zu reduzieren). Lassen Sie sich nicht vom „Größten“ im Namen täuschen – der GCF ist nicht größer als die kleinste der Zahlen.

COMMON ist etwas Gemeinsames oder Gemeinsames.

FAKTOREN sind die Teile von Multiplikationsfakten.

BEISPIEL:
Finden Sie den größten gemeinsamen Faktor (G.C.F.) von 6 und 10.

6 = 2 * 3 Sie können 6 durch 2 oder durch 3 teilen

6 = 1 * 6 Sie können 6 durch 1 oder durch 6 teilen

Daher sind 1, 2, 3 und 6 alles Faktoren von sechs.

10 = 2 * 5 Sie können 10 durch 2 oder durch 5 teilen

10 = 1 * 10 Sie können 10 durch 1 oder durch 10 teilen

Daher sind 1, 2, 5 und 10 alles Zehnerfaktoren.

Sowohl 6 als auch 10 können durch 1 und durch 2 geteilt werden 2 ist größer als 1, also ist 2 der größte gemeinsame Faktor (G.C.F.) von 6 und 10.

Sie können auch die Methode der Primfaktorzerlegung verwenden, um den größten gemeinsamen Faktor zu finden:


Inhalt

Definition Bearbeiten

Das größter gemeinsamer Teiler (GCD) zweier ganzer Zahlen a und b ist die größte positive ganze Zahl d, so dass d ein Teiler von a und b ist, d. h. es gibt ganze Zahlen e und f mit ein = de und b = df , und d ist die größte solche ganze Zahl. Die GCD von a und b wird allgemein als gcd(ein, b) . [9]

Diese Definition gilt auch, wenn eines von a und b null ist. In diesem Fall ist der GCD der absolute Wert der ganzen Zahl ungleich null: gcd(ein, 0) = gcd(0, ein) = | ein | . Dieser Fall ist als Abschlussschritt des euklidischen Algorithmus wichtig.

Die obige Definition kann nicht zur Definition von gcd(0, 0) verwendet werden, da 0 × nein = 0 , und null hat somit keinen größten Teiler. Null ist jedoch sein eigener größter Teiler, wenn größte wird im Kontext der Teilbarkeitsrelation verstanden, daher wird gcd(0, 0) allgemein als 0 definiert. Dadurch bleiben die üblichen Identitäten für GCD und insbesondere Bézouts Identität erhalten, nämlich dass gcd(ein, b) erzeugt dasselbe Ideal wie <ein, b> . [10] [11] [12] This convention is followed by many computer algebra systems. [13] Nonetheless, some authors leave gcd(0, 0) undefined. [14]

The GCD of a and b is their greatest positive common divisor in the preorder relation of divisibility. This means that the common divisors of a and b are exactly the divisors of their GCD. This is commonly proved by using either Euclid's lemma, the fundamental theorem of arithmetic, or the Euclidean algorithm. This is the meaning of "greatest" that is used for the generalizations of the concept of GCD.

Example Edit

The number 54 can be expressed as a product of two integers in several different ways:

54 × 1 = 27 × 2 = 18 × 3 = 9 × 6.

Of these, the greatest is 6, so it is the greatest common divisor:

Computing all divisors of the two numbers in this way is usually not efficient, especially for large numbers that have many divisors. Much more efficient methods are described in § Calculation.

Coprime numbers Edit

Two numbers are called relatively prime, or coprime, if their greatest common divisor equals 1. [15] For example, 9 and 28 are relatively prime.

A geometric view Edit

For example, a 24-by-60 rectangular area can be divided into a grid of: 1-by-1 squares, 2-by-2 squares, 3-by-3 squares, 4-by-4 squares, 6-by-6 squares or 12-by-12 squares. Therefore, 12 is the greatest common divisor of 24 and 60. A 24-by-60 rectangular area can thus be divided into a grid of 12-by-12 squares, with two squares along one edge (24/12 = 2) and five squares along the other (60/12 = 5).

Reducing fractions Edit

The greatest common divisor is useful for reducing fractions to the lowest terms. [16] For example, gcd(42, 56) = 14, therefore,

Least common multiple Edit

The greatest common divisor can be used to find the least common multiple of two numbers when the greatest common divisor is known, using the relation, [1]

Using prime factorizations Edit

Greatest common divisors can be computed by determining the prime factorizations of the two numbers and comparing factors. For example, to compute gcd(48, 180), we find the prime factorizations 48 = 2 4 · 3 1 and 180 = 2 2 · 3 2 · 5 1 the GCD is then 2 min(4,2) · 3 min(1,2) · 5 min(0,1) = 2 2 · 3 1 · 5 0 = 12, as shown in the Venn diagram. The corresponding LCM is then 2 max(4,2) · 3 max(1,2) · 5 max(0,1) = 2 4 · 3 2 · 5 1 = 720.

In practice, this method is only feasible for small numbers, as computing prime factorizations takes too long.

Euclid's algorithm Edit

The method introduced by Euclid for computing greatest common divisors is based on the fact that, given two positive integers a and b such that ein > b , the common divisors of a and b are the same as the common divisors of einb and b .

So, Euclid's method for computing the greatest common divisor of two positive integers consists of replacing the larger number by the difference of the numbers, and repeating this until the two numbers are equal: that is their greatest common divisor.

For example, to compute gcd(48,18) , one proceeds as follows:

This method can be very slow if one number is much larger than the other. So, the variant that follows is generally preferred.

Euclidean algorithm Edit

A more efficient method is the Euclidean algorithm, a variant in which the difference of the two numbers a and b is replaced by the Rest of the Euclidean division (also called division with remainder) of a by b .

Denoting this remainder as ein mod b , the algorithm replaces (ein, b) by (b, ein mod b) repeatedly until the pair is (d, 0) , where d is the greatest common divisor.

For example, to compute gcd(48,18), the computation is as follows:

This again gives gcd(48, 18) = 6 .

Lehmer's GCD algorithm Edit

Lehmer's algorithm is based on the observation that the initial quotients produced by Euclid's algorithm can be determined based on only the first few digits this is useful for numbers that are larger than a computer word. In essence, one extracts initial digits, typically forming one or two computer words, and runs Euclid's algorithms on these smaller numbers, as long as it is guaranteed that the quotients are the same with those that would be obtained with the original numbers. Those quotients are collected into a small 2-by-2 transformation matrix (that is a matrix of single-word integers), for using them all at once for reducing the original numbers [ Klärung nötig ] . This process is repeated until numbers are small enough that the binary algorithm (see below) is more efficient.

This algorithm improves speed, because it reduces the number of operations on very large numbers, and can use hardware arithmetic for most operations. In fact, most of the quotients are very small, so a fair number of steps of the Euclidean algorithm can be collected in a 2-by-2 matrix of single-word integers. When Lehmer's algorithm encounters a quotient that is too large, it must fall back to one iteration of Euclidean algorithm, with a Euclidean division of large numbers.

Binary GCD algorithm Edit

The binary GCD algorithm uses only subtraction and division by 2. The method is as follows: Let ein und b be the two non-negative integers. Let the integer d be 0. There are five possibilities:

As gcd(ein, ein) = ein, the desired GCD is ein × 2 d (as ein und b are changed in the other cases, and d records the number of times that ein und b have been both divided by 2 in the next step, the GCD of the initial pair is the product of ein and 2 d ).

Then 2 is a common divisor. Divide both ein und b by 2, increment d by 1 to record the number of times 2 is a common divisor and continue.

Then 2 is not a common divisor. Divide ein by 2 and continue.

Then 2 is not a common divisor. Divide b by 2 and continue.

As gcd(ein,b) = gcd(b,ein), if ein < b then exchange ein und b. Die Nummer c = einb is positive and smaller than ein. Any number that divides ein und b must also divide c so every common divisor of ein und b is also a common divisor of b und c. Ähnlich, ein = b + c and every common divisor of b und c is also a common divisor of ein und b. So the two pairs (ein, b) and (b, c) have the same common divisors, and thus gcd(ein,b) = gcd(b,c). Moreover, as ein und b are both odd, c is even, the process can be continued with the pair (ein, b) replaced by the smaller numbers (c/2, b) without changing the GCD.

Each of the above steps reduces at least one of ein und b while leaving them non-negative and so can only be repeated a finite number of times. Thus eventually the process results in ein = b, the stopping case. Then the GCD is ein × 2 d .

Example: (ein, b, d) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1) the original GCD is thus the product 6 of 2 d = 2 1 and ein= b= 3.

The binary GCD algorithm is particularly easy to implement on binary computers. Its computational complexity is

The computational complexity is usually given in terms of the length n of the input. Here, this length is n = log ⁡ a + log ⁡ b , and the complexity is thus

Other methods Edit

If ein und b are both nonzero, the greatest common divisor of ein und b can be computed by using least common multiple (LCM) of ein und b:

but more commonly the LCM is computed from the GCD.

which generalizes to ein und b rational numbers or commensurable real numbers.

Keith Slavin has shown that for odd ein ≥ 1:

which is a function that can be evaluated for complex b. [18] Wolfgang Schramm has shown that

is an entire function in the variable b for all positive integers ein wo cd(k) is Ramanujan's sum. [19]

Complexity Edit

The computational complexity of the computation of greatest common divisors has been widely studied. [20] If one uses the Euclidean algorithm and the elementary algorithms for multiplication and division, the computation of the greatest common divisor of two integers of at most n bits is O ( n 2 ) . ).> This means that the computation of greatest common divisor has, up to a constant factor, the same complexity as the multiplication.

However, if a fast multiplication algorithm is used, one may modify the Euclidean algorithm for improving the complexity, but the computation of a greatest common divisor becomes slower than the multiplication. More precisely, if the multiplication of two integers of n bits takes a time of T(nein) , then the fastest known algorithm for greatest common divisor has a complexity O ( T ( n ) log ⁡ n ) . This implies that the fastest known algorithm has a complexity of O ( n ( log ⁡ n ) 2 ) . ight).>

Previous complexities are valid for the usual models of computation, specifically multitape Turing machines and random-access machines.

The computation of the greatest common divisors belongs thus to the class of problems solvable in quasilinear time. A fortiori, the corresponding decision problem belongs to the class P of problems solvable in polynomial time. The GCD problem is not known to be in NC, and so there is no known way to parallelize it efficiently nor is it known to be P-complete, which would imply that it is unlikely to be possible to efficiently parallelize GCD computation. Shallcross et al. showed that a related problem (EUGCD, determining the remainder sequence arising during the Euclidean algorithm) is NC-equivalent to the problem of integer linear programming with two variables if either problem is in NC or is P-complete, the other is as well. [21] Since NC contains NL, it is also unknown whether a space-efficient algorithm for computing the GCD exists, even for nondeterministic Turing machines.

Although the problem is not known to be in NC, parallel algorithms asymptotically faster than the Euclidean algorithm exist the fastest known deterministic algorithm is by Chor and Goldreich, which (in the CRCW-PRAM model) can solve the problem in O(nein/log nein) time with nein 1+ε processors. [22] Randomized algorithms can solve the problem in O((log nein) 2 ) time on exp ⁡ ( O ( n log ⁡ n ) ) > ight) ight)> processors [ Klärung nötig ] (this is superpolynomial). [23]

  • Every common divisor of ein und b is a divisor of gcd(ein, b) .
  • gcd(ein, b) , where ein und b are not both zero, may be defined alternatively and equivalently as the smallest positive integer d which can be written in the form d = einp + bq , wo p und q are integers. This expression is called Bézout's identity. Numbers p und q like this can be computed with the extended Euclidean algorithm.
  • gcd(ein, 0) = | ein | , for ein ≠ 0 , since any number is a divisor of 0, and the greatest divisor of ein is | ein |. [3][6] This is usually used as the base case in the Euclidean algorithm.
  • If ein divides the product bc, and gcd(ein, b) = d , dann ein/d divides c.
  • If ich is a non-negative integer, then gcd(ichein, ichb) = ich⋅gcd(ein, b) .
  • If ich is any integer, then gcd(ein + ichb, b) = gcd(ein, b) .
  • If ich is a positive common divisor of ein und b, then gcd(ein/ich, b/ich) = gcd(ein, b)/ich .
  • The GCD is a multiplicative function in the following sense: if ein1 und ein2 are relatively prime, then gcd(ein1ein2, b) = gcd(ein1, b)⋅gcd(ein2, b) . In particular, recalling that GCD is a positive integer valued function we obtain that gcd(ein, bc) = 1 if and only if gcd(ein, b) = 1 and gcd(ein, c) = 1 .
  • The GCD is a commutative function: gcd(ein, b) = gcd(b, ein) .
  • The GCD is an associative function: gcd(ein, gcd(b, c)) = gcd(gcd(ein, b), c) . Thus gcd(ein, b, c, . ) can be used to denote the GCD of multiple arguments.
  • gcd(ein, b) is closely related to the least common multiple lcm(ein, b) : we have gcd(ein, b)⋅lcm(ein, b) = | einb | .
  • The following versions of distributivity hold true: gcd(ein, lcm(b, c)) = lcm(gcd(ein, b), gcd(ein, c)) lcm(ein, gcd(b, c)) = gcd(lcm(ein, b), lcm(ein, c)) .
  • If we have the unique prime factorizations of ein = p1e1p2e2 ⋅⋅⋅ picheich und b = p1f1p2f2 ⋅⋅⋅ pichfich wo eich ≥ 0 und fich ≥ 0 , then the GCD of ein und b is gcd(ein,b) = p1 min(e1,f1) p2 min(e2,f2) ⋅⋅⋅ pich min(eich,fich) .
  • It is sometimes useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a completedistributive lattice with GCD as meet and LCM as join operation. [24] This extension of the definition is also compatible with the generalization for commutative rings given below.
  • In a Cartesian coordinate system, gcd(ein, b) can be interpreted as the number of segments between points with integral coordinates on the straight line segment joining the points (0, 0) and (ein, b) .
  • For non-negative integers ein und b, wo ein und b are not both zero, provable by considering the Euclidean algorithm in base nein: [25] gcd(neinein − 1, neinb − 1) = nein gcd(ein,b) − 1 .
  • An identity involving Euler's totient function: gcd ( a , b ) = ∑ k | a and k | b φ ( k ) . >k|b>varphi (k).>

In 1972, James E. Nymann showed that k integers, chosen independently and uniformly from <1, . nein>, are coprime with probability 1/ζ(k) as nein goes to infinity, where ζ refers to the Riemann zeta function. [26] (See coprime for a derivation.) This result was extended in 1987 to show that the probability that k random integers have greatest common divisor d is d −k /ζ(k). [27]

Using this information, the expected value of the greatest common divisor function can be seen (informally) to not exist when k = 2. In this case the probability that the GCD equals d is d −2 /ζ(2), and since ζ(2) = π 2 /6 we have

This last summation is the harmonic series, which diverges. However, when k ≥ 3, the expected value is well-defined, and by the above argument, it is

Zum k = 3, this is approximately equal to 1.3684. Zum k = 4, it is approximately 1.1106.

The notion of greatest common divisor can more generally be defined for elements of an arbitrary commutative ring, although in general there need not exist one for every pair of elements.

If R is a commutative ring, and a and b are in R , then an element d of R is called a common divisor of a and b if it divides both a and b (that is, if there are elements x and y in R such that d·x = ein und d·ja = b). If d is a common divisor of a and b , and every common divisor of a and b divides d , then d is called a greatest common divisor of a and b.

With this definition, two elements a and b may very well have several greatest common divisors, or none at all. If R is an integral domain then any two GCD's of a and b must be associate elements, since by definition either one must divide the other indeed if a GCD exists, any one of its associates is a GCD as well. Existence of a GCD is not assured in arbitrary integral domains. However, if R is a unique factorization domain, then any two elements have a GCD, and more generally this is true in GCD domains. If R is a Euclidean domain in which euclidean division is given algorithmically (as is the case for instance when R = F[X] where F is a field, or when R is the ring of Gaussian integers), then greatest common divisors can be computed using a form of the Euclidean algorithm based on the division procedure.

The following is an example of an integral domain with two elements that do not have a GCD:

The elements 2 and 1 + √ −3 are two maximal common divisors (that is, any common divisor which is a multiple of 2 is associated to 2, the same holds for 1 + √ −3 , but they are not associated, so there is no greatest common divisor of a and b.

Corresponding to the Bézout property we may, in any commutative ring, consider the collection of elements of the form pa + qb, where p and q range over the ring. This is the ideal generated by a and b , and is denoted simply (ein, b). In a ring all of whose ideals are principal (a principal ideal domain or PID), this ideal will be identical with the set of multiples of some ring element d then this d is a greatest common divisor of a and b. But the ideal (ein, b) can be useful even when there is no greatest common divisor of a and b. (Indeed, Ernst Kummer used this ideal as a replacement for a GCD in his treatment of Fermat's Last Theorem, although he envisioned it as the set of multiples of some hypothetical, or ideal, ring element d , whence the ring-theoretic term.)


How to Find the Greatest Common Factor of Decimal Numbers?

The largest decimal that is a factor of two or more decimal points that divide evenly is known as the Greatest common factor of decimals (In short, GCF of Decimals).

To find the GCD of Decimals, you have to follow the below instructions carefully and make your Greatest common factor of decimal numbers calculations easy by hand. They are as under

  • First and foremost, you need to change the given decimal points into integers with the help of multiplication of 10, 100, 1000.
  • After that, find the decimal which is having more digits after decimal points. For suppose, it has two digits after decimal point then multiply the given numbers with 100 and convert into integers.
  • Now you have to perform finding the Greatest common factor(GCF) of the integers you get in step 1.
  • Once you find the GCF of integers then convert the result into a decimal by dividing with 100 (the number that you multiplied the given decimals in step 1).
  • Finally, you will get the Greatest Common Factor of given decimals easily by hand.

Have a look at the worked-out example presented here and understand the concept behind the Finding GCF of Decimals to get a good grip on it.

Find the GCF of 3.09 and 0.6?

Given decimals are 3.09, 0.6.

In the given decimals, the highest digits having after the decimal point is 3.09, it has two digits so we have to multiply the both given decimals ie., 3.09 and 0.6 with 100.

After multiplying by 100, we get the decimals in integers as 309 and 60

Now we need to find the GCF of 309 and 60, to get the GCF of decimals

Here we are using a common division method to find the GCF of two numbers 309, 60.

Later, convert the GCF of integer result into decimals to get the Greatest Common Factor of decimals 3.09 and 0.6

In the final step, we need to divide the GCF of 309 and 60 with 100 (which is used in converting decimals to integers in step 1)

Once you divide, GCF/100 = 3/100, we get 0.03 the greatest factor that divides given decimals exactly.


Beispiele

Greatest Common Divisors of Double Values

gcd returns positive values, even when the inputs are negative.

Greatest Common Divisors of Unsigned Integers

Solution to Diophantine Equation

Solve the Diophantine equation, 3 0 x + 5 6 y = 8 for x and y .

Find the greatest common divisor and a pair of Bézout coefficients for 30 and 56 .

u and v satisfy the Bézout's identity, (30*u) + (56*v) = g .

Rewrite Bézout's identity so that it looks more like the original equation. Do this by multiplying by 4 . Use == to verify that both sides of the equation are equal.

Calculate the values of x and y that solve the problem.


Logic and Discrete Mathematics: A Concise Introduction

This book features a unique combination of comprehensive coverage of logic with a solid exposition of the most important fields of discrete mathematics, presenting material that has been tested and refined by the authors in university courses taught over more than a decade.

The chapters on logic - propositional and first-order - provide a robust toolkit for logical reasoning, emphasizing the conceptual understanding of the language and the semantics of classical logic as well as practical applications through the easy to understand and use deductive systems of Semantic Tableaux and Resolution. The chapters on set theory, number theory, combinatorics and graph theory combine the necessary minimum of theory with numerous examples and selected applications. Written in a clear and reader-friendly style, each section ends with an extensive set of exercises, most of them provided with complete solutions which are available in the accompanying solutions manual.

  • Suitable for a variety of courses for students in both Mathematics and Computer Science.
  • Extensive, in-depth coverage of classical logic, combined with a solid exposition of a selection of the most important fields of discrete mathematics
  • Concise, clear and uncluttered presentation with numerous examples.
  • Covers some applications including cryptographic systems, discrete probability and network algorithms.

Logic and Discrete Mathematics: A Concise Introduction is aimed mainly at undergraduate courses for students in mathematics and computer science, but the book will also be a valuable resource for graduate modules and for self-study.


Schau das Video: Sätze zum ggT Teil 1 (November 2021).