Mathematische Grundlagen
Teilbarkeit
 – Video
Video anzeigen

Du hast vom euklidischen Algorithmus gehört und möchtest verstehen, wie er funktioniert? Hier bekommst du eine Schritt-für-Schritt-Anleitung!%Schau dir auch gerne unser Video dazu an. 

Euklidischer Algorithmus einfach erklärt

Den euklidischen Algorithmus verwendest du, um den größten gemeinsamen Teiler (ggT) von zwei Zahlen zu bestimmen. Deshalb kannst du ihn auch ggT Algorithmus nennen.

Am folgenden Beispiel siehst du, wie man den euklidischen Algorithmus durchführt. 

Was ist der ggT von 132 und 28?

Rechenschritt Euklidischer Algorithmus Erklärung euklidischer Algorithmus 
132 = 4 · 28 + 20

Schritt 1:
Mache eine Division mit Rest.
Teile dabei die größere Zahl (Dividend: 132) durch die kleinere (Divisor: 28).
132 : 28 = 4 Rest 20
Du kannst also 132 schreiben als 4 · 28 + 20.

28 = 1 · 20 + 8  Schritt 2:
Nun teilst du 28 durch 20.
Der Divisor aus Schritt 1 (28) wird also zum Dividenden und der vorige Rest (20) zum  Divisor.
28 : 20 = 1 Rest 8
Damit kannst du nun 28 als 1 · 20 + 8 darstellen.
20 = 2 · 8 + 4 In den folgenden Schritten wiederholst du das Prinzip aus Schritt 2:
Alter Divisor (20) wird neuer Dividend,
alter Rest (8) wird neuer Divisor. 
8 = 2 · 4 + 0 Letzter Schritt:
Das wiederholst du so lange, bis die Division den Rest 0 ergibt.
Nun kannst du den gesuchten ggT ganz einfach ablesen: Es ist der Divisor in der letzten Rechnung, also der letzte Rest, der nicht 0 war.

Das Ergebnis des Euklid Algorithmus ist also ggT(132,28) = 4.

Euklidischer Algorithmus — Mathematische Schreibweise  

In allgemeiner mathematischer Form aufgeschrieben sieht der euklidische Algorithmus so aus:  

Gegeben sind zwei Zahlen a und b und gesucht ist ihr größter gemeinsamer Teiler ggT(a,b).

Rechenschritt Euklidischer Algorithmus Erklärung euklidischer Algorithmus
a = q0 · b + r0 Die Division mit Rest a : b liefert einen Quotienten qund einen Rest r0
b = q1 · r0 + r1 Ab dann folgst du immer demselben Prinzip:
  • DivisorDividend 
  • Rest      → Divisor 
  • Division mit Rest durchführen
r0 = q2 · r1 + r2
 
rn-3 = qn-1 · rn-2 + rn-1 Der Rest, und damit auch der neue Divisor, wird in jedem Schritt kleiner. Spätestens wenn du durch 1 teilst, erhältst du Rest 0.
Somit endet der Euklid Algorithmus immer nach endlich vielen Schritten.
rn-2 = qn · rn-1 + 0 Wenn der Rest 0 ist, kannst du den ggT direkt ablesen:
Es ist der Divisor im letzten Schritt des euklidischen Algorithmus, also der letzte Rest, der nicht 0 ist.

Merke: Falls die Division tatsächlich erst mit dem Divisor 1 Rest 0 ergibt, bedeutet das, dass die Zahlen a und b die 1 als größten gemeinsamen Teiler haben. 
In diesem Fall nennt man a und b dann teilerfremd.

Euklidischer Algorithmus Schritt-für-Schritt

Gegeben: Zwei Zahlen a und b
Gesucht: ggT(a,b)

    1. Division mit Rest a : b.
    2. DivisorDividend,
      Rest      → Divisor
      Damit: wieder Division mit Rest.
    3. Wiederhole Schritt 2, bis Rest 0 herauskommt. 
    4. ggT(a,b) = letzter Rest, der nicht 0 war.

Übrigens: Durch Umstellen der Formel a · b = ggT(a,b) · kgV(a,b) kannst du das Ergebnis des euklidischen Algorithmus auch verwenden, um das kleinste gemeinsame Vielfache (kgV) von zwei Zahlen zu bestimmen. 

Chinesischer Restsatz

Du verstehst jetzt, was du tun sollst, wenn in einer Aufgabe etwas mit „Euklidischer Algorithmus“ steht? Super! Dann schau unbedingt auch mal bei unserem Beitrag zum chinesischen Restsatz vorbei! %Thumbnail Chinesischer Restsatz 

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.