Euklidischer Algorithmus – Bestimmung des ggT
Der euklidische Algorithmus ist eine Methode, um den größten gemeinsamen Teiler von zwei natürlichen Zahlen durch Subtraktion oder Division zu finden. Er wurde von Euklid entwickelt und ermöglicht es, den ggT auch bei größeren Zahlen schnell zu bestimmen. Interessiert? Dann lies weiter im Text!
in nur 12 Minuten? Du willst ganz einfach ein neues
Thema lernen in nur 12 Minuten?
-
5 Minuten verstehen
Unsere Videos erklären Ihrem Kind Themen anschaulich und verständlich.
92%der Schüler*innen hilft sofatutor beim selbstständigen Lernen. -
5 Minuten üben
Mit Übungen und Lernspielen festigt Ihr Kind das neue Wissen spielerisch.
93%der Schüler*innen haben ihre Noten in mindestens einem Fach verbessert. -
2 Minuten Fragen stellen
Hat Ihr Kind Fragen, kann es diese im Chat oder in der Fragenbox stellen.
94%der Schüler*innen hilft sofatutor beim Verstehen von Unterrichtsinhalten.
5 Minuten verstehen
5 Minuten üben
2 Minuten Fragen stellen
Bereit für eine echte Prüfung?
Grundlagen zum Thema Euklidischer Algorithmus – Bestimmung des ggT
Euklidischer Algorithmus – Definition
Der euklidische Algorithmus ist ein Verfahren zur Bestimmung des größten gemeinsamen Teilers ($\text{ggT}$) zweier natürlicher Zahlen. Entwickelt wurde dieser Algorithmus vom griechischen Mathematiker Euklid. Der $\text{ggT}$ zweier natürlicher Zahlen, die kleiner als $100$ sind, lässt sich noch vergleichsweise einfach bestimmen. Bei größeren Zahlen kann der euklidische Algorithmus helfen, den $\text{ggT}$ vergleichsweise schnell zu bestimmen.
Grundgedanke
Euklid machte sich bei der Entwicklung des Verfahrens die Summenregel der Teilbarkeit zweier Zahlen zunutze. Diese besagt: Teilt eine Zahl $a$ ohne Rest die Zahl $b$ und die Zahl $c$, dann teilt $a$ auch die Summe und die Differenz aus $b$ und $c$ (für $b>c$) ohne Rest. Zur Verdeutlichung dient folgendes Beispiel:
- $7 \mid 21$, also $7$ ist ein Teiler von $21$.
- $7 \mid 70$, $7$ ist ebenfalls ein Teiler von $70$.
- $7 \mid (21+70)$ und $7 \mid (70-21)$ bedeutet demnach, dass $7$ auch die Summe sowie die Differenz aus $70$ und $21$ teilt, denn $(70+21):7=91:7=13$ und $(70-21):7=49:7=7$.
Der Teiler größerer Zahlen lässt sich jedoch nicht immer so leicht herausfinden. Hier hilft der euklidische Algorithmus.
$\text{ggT}$: Algorithmus allgemein
Es gibt zwei Varianten, mittels des euklidischen Algorithmus den $\text{ggT}$ zweier Zahlen zu bestimmen. Zum einen kann der Algorithmus durch Subtraktion und zum anderen durch Division der beiden zu untersuchenden Zahlen durchgeführt werden.
Bei der Subtraktion wird wie folgt vorgegangen:
- $1.$ Schritt: Ziehe die kleinere Zahl von der größeren Zahl ab.
- $2.$ Schritt: Wiederhole Schritt $1$ so lange, bis der Wert der Differenz kleiner als der Subtrahend ist.
- $3.$ Schritt: Ziehe dann den Wert der Differenz vom Subtrahenden ab.
- $4.$ Schritt: Die Schritte $1$ bis $3$ so oft wiederholen, bis Differenz und Subtrahend gleich sind. Das ist der gesuchte $\text{ggT}$.
Bei der Division geht man folgendermaßen vor:
- $1.$ Schritt: Teile die größere durch die kleinere Zahl (Division mit Rest).
- $2.$ Schritt: Teile den Divisor der ersten Rechnung durch den entstandenen Rest.
- $3.$ Schritt: Wiederhole die ersten beiden Schritte, bis bei der Division kein Rest mehr bleibt. Der letzte Divisor ist der gesuchte $\text{ggT}$.
Beispiele – Wie bestimmt man den ggT für ggT:(360;105)
Für die Subtraktion kann man folgendermaßen vorgehen:
$\begin{array}{rcrcrcl} 360&-&105&=&255&&\\ 255&-&105&=&150&&\\ 150&-&105&=&45&\vert&45<105\\ 105&-&45&=&60&&\\ 60&-&45&=&15&\vert&15<45\\ 45&-&15&=&30&&\\ 30&-&\underline{15}&=&\underline{15}&\vert&\text{ggT}(360;105)=15 \end{array}$
Wird für das Verfahren die Division verwendet, geht man so vor:
$\begin{array}{rcrcrcl} 360&:&105&=&3&\vert&\text{Rest}~45\\ 105&:&45&=&2&\vert&\text{Rest}~15\\ 45&:&\underline{15}&=&3&\vert&\text{Rest}~\underline{0}\\ &&&&&&\text{ggT}(360;105)=15 \end{array}$
$\text{ggT}$ von $1071$ und $1029$
$\begin{array}{rcrclrl} 1079&:&1029&=&1&\vert&\text{Rest}~42\\ 1029&:&42&=&24&\vert&\text{Rest}~21\\ 42&:&\underline{21}&=&2&\vert&\text{Rest}~\underline{0}\\ &&&&&&\text{ggT}(1071;1029)=21 \end{array}$
Euklidischer Algorithmus –Verwendung
An den Beispielen ist zu erkennen, dass mit dem euklidischen Algorithmus auch der größte gemeinsame Teiler zweier vierstelliger und auch größerer Zahlen verhältnismäßig schnell bestimmt werden kann, wenn die Grundlagen der Division mit Rest beherrscht werden.
Einschränkungen des Algorithmus
Dieses Verfahren kann jedoch nur für die Bestimmung des $\text{ggT}$ von zwei Zahlen genutzt werden. Bei drei und mehr Zahlen ist ein anderes Verfahren zu verwenden.
Im Falle mehrerer Zahlen bietet sich beispielsweise das Finden des $\text{ggT}$ über die Primfaktorzerlegung oder über die Betrachtung der Teilermengen an.
Transkript Euklidischer Algorithmus – Bestimmung des ggT
Hallo, da bin ich wieder, eure Sabine Blumenthal!In diesem Video erkläre ich dir den euklidischen Algorithmus. Du lernst, was das ist, und du lernst die Rechenverfahren von Euklid kennen. Das solltest du bereits wissen: Die Summenregel der Teilbarkeit Natürlicher Zahlen, was ein ggT ist, du solltest die Subtraktion Natürlicher Zahlen können und auch die Division Natürlicher Zahlen. Der euklidische Algorithmus, was ist das überhaupt? Nun, das ist eine Möglichkeit, den ggT von zwei Zahlen zu bestimmen. Es ist ein Rechenverfahren, welches vor mehr als 2000 Jahren von Euklid erdacht wurde. Den Namen Euklid solltest du dir schon einmal merken. Hier siehst du ein Bild von Euklid. Er lebte ungefähr um 300 vor Christus, also vor mehr als 2000 Jahren. Er war ein griechischer Mathematiker und hat sich unter anderem dieses Verfahren ausgedacht, um den ggT von zwei Zahlen zu bestimmen. Euklid nutzte für seinen Algorithmus die Summenregel der Teilbarkeit. Erinnere dich an diese Regel zur Teilbarkeit Natürlicher Zahlen. Sie lautet: Wenn zwei Zahlen einen gemeinsamen Teiler haben, wie hier im Beispiel die 21 und die 70, dann teilt dieser gemeinsame Teiler auch die Summe beziehungsweise die Differenz der zwei Zahlen. In unserem Beispiel ist die sieben also auch ein Teiler der Summe 21 plus 70 beziehungsweise der Differenz 70 minus 21. Sieben ist ein Teiler von 91, weil 713=91 ist und sieben ist ein Teiler von 49, weil 77=49 ist. Nun ist das Finden gemeinsamer Teiler bei Zahlen im Bereich des kleinen Einmaleins, also bis etwa zur 100, nicht so schwierig. Bei großen Zahlen kann das Finden von gemeinsamen Teilern oder des ggT sehr mühsam sein. In einem solchen Fall kann uns der von Euklid gefundene Algorithmus helfen. Algorithmus bedeutet, dass gleiche Handlungen in einer bestimmten Reihenfolge immer wiederholt werden. Euklid wiederholte immer die gleiche Folge von Rechenschritten, deshalb bedeutet Algorithmus hier soviel wie Rechenkette. Schauen wir uns die Abfolge der Rechenschritte an einem Beispiel an: Wir wollen den ggT von 360 und 105 bestimmen. Damit du die einzelnen Schritte gut nachvollziehen kannst, habe ich die Subtrahenden immer in rot und die Ergebnisse in grün geschrieben. Ich spreche in der Erklärung auch von roten und grünen Zahlen. Das ist mathematisch zwar nicht so ganz exakt, aber so kannst du den Rechenweg besser nachvollziehen. Doch nun endlich zu unserer Rechenkette. Der erste Schritt: Ziehe die kleinere Zahl von der größeren ab. Du rechnest also 360 minus 105 und erhältst 255. Der zweite Schritt lautet: wiederhole den ersten Schritt so lange, bis der Rest, also die grüne Zahl, kleiner als die rote Zahl ist. Im dritten Schritt heißt es: ziehe nun den Rest, also die grüne Zahl, von dem letzten Subtrahenden, also der roten Zahl, ab. Hier ist 45 kleiner als 105. Also rechnest du jetzt 105 minus 45 und erhältst 60. Du vergleichst wieder die grüne und die rote Zahl. Ist die grüne Zahl größer als die rote, beginnst du wieder bei Schritt eins und das Ganze geht von vorne los. Der vierte Schritt ist ganz einfach. Wiederhole die Schritte eins bis drei so lange, bis die rote und die grüne Zahl gleich groß sind. Wenn du das erreicht hast, dann hast du den ggT gefunden. Rote Zahl gleich grüne Zahl, das heißt, diese Zahl ist der gesuchte ggT. 15 ist also der ggT von 360 und 105. Dieses Verfahren mit Subtraktionen erleichtert zwar das Finden des ggT von zwei großen Zahlen, aber es ist doch manchmal ziemlich lang und zeitaufwendig. Und du ahnst es schon, auch dieses Verfahren kann man abkürzen. Dank Herrn Euklid gibt es auch einen Algorithmus mit Divisionen. Wir bleiben bei unserem Beispiel, den ggT von 360 und 105 zu bestimmen. Dann kannst du beide Verfahren besser miteinander vergleichen. Der erste Schritt heißt jetzt: teile die größere durch die kleinere Zahl. Du solltest jetzt also die Division mit Rest gut beherrschen. Teile also 360 durch 105, du erhältst drei und es bleibt ein Rest von 45, den ich in grün schreibe. Der zweite Schritt lautet: teile die kleinere, also die rote, Zahl durch den Rest, also durch die grüne Zahl. 105 geteilt durch 45 ist gleich zwei, denn zweimal 45 ist 90, und es bleibt ein Rest von 15. Der dritte Schritt sagt: wiederhole Schritt zwei solange, bis bei der Division der Rest null bleibt. 45/15=3, Rest null. Damit ist der Algorithmus beendet, du hast den ggT gefunden. Die letzte Zahl, durch die du geteilt hast, also der letzte Divisor oder ganz einfach die letzte rote Zahl, ist dein gesuchter ggT. Und nun gibts zum euklidischen Algorithmus noch eine kurze Zusammenfassung: Der bedeutende griechische Mathematiker Euklid fand vor über 2000 Jahren ein Rechenverfahren heraus, um den ggT zweier Zahlen zu bestimmen, den nach ihm benannten Euklidischen Algorithmus. Euklid fand sogar zwei Möglichkeiten seines Algorithmus heraus: eine Subtraktionskette und eine Divisionskette. Na, hast du trotz der vielen Zahlen und Rechenschritte alles gut verstehen können? Prima! Dann tschüss, bis zum nächsten Mal!
Euklidischer Algorithmus – Bestimmung des ggT Übung
-
Ergänze die Erklärung zum euklidischen Algorithmus.
TippsAchte im 2. Schritt und 4. Schritt auf die Reihenfolge.
Merke dir:
Minuend $-$ Subtrahend $=$ Differenz.
LösungEuklid von Alexandria war ein griechischer Mathematiker. Man vermutet, dass er im 3. Jahrhundert v. Chr. in Alexandria gelebt hat.
Auf Euklid geht der hier vorgestellte Algorithmus zum Bestimmen eines größten gemeinsamen Teilers zweier Zahlen zurück. Er verwendet dabei die Summenregel für die Teilbarkeit: Wenn zwei Zahlen einen gemeinsamen Teiler haben, dann teilt dieser Teiler auch die Summe sowie die Differenz der beiden Zahlen.
Ein Algorithmus ist eine Abfolge von immer gleichen Rechenschritten. Schließlich soll der Algorithmus zu einem Ergebnis, hier dem größten gemeinsamen Teiler zweier Zahlen, führen.
1. Schritt: Bilde die Differenz der beiden Zahlen. Ziehe hierfür von der größeren die kleinere ab. Du erhältst dann $360-105=255$.
2. Schritt: Wiederhole den 1. Schritt so lange, bis der Rest, sprich die Differenz, kleiner ist als der Subtrahend:
- $255-105=150$
- $150-105=45$: Du siehst, die Differenz $45$ ist kleiner als der Subtrahend $105$.
4. Schritt: Wiederhole die ersten drei Schritte so lange, bis der Subtrahend und die Differenz übereinstimmen:
- $60-45=15$
- $45-15=30$
- $30-15=15$: Nun stimmen Subtrahend $15$ und Differenz $15$ überein. Dies ist der gesuchte größte gemeinsame Teiler.
-
Bestimme den größten gemeinsamen Teiler der beiden Zahlen.
TippsMerke dir:
Dividend $:$ Divisor $=$ Quotient.
Beim Teilen mit Rest schaust du immer, wie oft der Divisor „ganz“ in den Dividenden passt. Schau dir $45:12$ als Beispiel an:
- Es ist $3\cdot 12=36$ und $45-36=9$.
- So erhältst du $45:12=3$ Rest $9$.
Der Rest ist immer kleiner als der Divisor.
LösungEuklid hat ganz schön viel für die Mathematik getan. Dazu gehört auch ein Algorithmus zur Bestimmung eines größten gemeinsamen Teilers mit Hilfe der Division.
1. Schritt: Dividiere die größere Zahl durch die kleinere. Ist dies ohne Rest möglich, so ist die kleinere Zahl der größte gemeinsame Teiler. Hier erhältst du $360:105=3$. Es bleibt ein Rest von $360-3\cdot 105=360-315=45$.
2. Schritt: Teile nun den Divisor, also $105$, durch den Rest, hier $45$. Du rechnest $105:45=2$ Rest $15$.
3. Schritt: Wiederhole nun den 2. Schritt so lange, bis du einen Rest $0$ erhältst. Dies ist im nächsten Schritt der Fall. Dieser ergibt $45:15=3$ Rest $0$.
Der letzte Divisor, hier die $15$, ist der gesuchte größte gemeinsame Teiler:
ggT$(360;105)=15$.
-
Ermittle den größten gemeinsamen Teiler von $60$ sowie $96$ mit Hilfe von Differenzen.
TippsHier siehst du noch einmal das allgemeine Vorgehen:
1. Schritt: Bilde die Differenz der beiden Zahlen. Ziehe hierfür von der größeren die kleinere ab.
2. Schritt: Wiederhole den 1. Schritt so lange, bis die Differenz kleiner ist als der Subtrahend.
3. Schritt: Ziehe von dem Subtrahenden die Differenz ab.
4. Schritt: Wiederhole die ersten drei Schritte so lange, bis der Subtrahend und die Differenz übereinstimmen.
Am Ende dieses Algorithmus hast du den größten gemeinsamen Teiler gefunden.
LösungIn dieser Aufgabe kannst du den Algorithmus, der auf Differenzen basiert, an etwas kleineren Zahlen üben. Dieser Algorithmus funktioniert bei beliebigen natürlichen Zahlen.
1. Schritt: Bilde die Differenz der beiden Zahlen. Ziehe hierfür von der größeren die kleinere ab:
$96-60=36$
2. Schritt: Wiederhole den 1. Schritt so lange, bis die Differenz kleiner ist als der Subtrahend. Dies ist hier bereits der Fall.
3. Schritt: Subtrahiere nun vom Subtrahenden die Differenz.
Du erhältst dann $60-36=24$.
4. Schritt: Wiederhole die ersten drei Schritte so lange, bis der Subtrahend und die Differenz übereinstimmen.
- $36-24=12$
- $24-12=12$
ggT$(60;96)=12$.
-
Leite den größten gemeinsamen Teiler von $48$ und $246$ durch Division her.
TippsTeile immer den Divisor durch den vorherigen Rest. Wenn das Ergebnis $0$ ist, ist der Divisor dieser Rechnung der größte gemeinsame Teiler.
Die Bezeichnungen bei der Division lauten wie folgt:
Dividend $:$ Divisor $=$ Quotient.
Hier siehst du ein Beispiel für die Ermittlung des größten gemeinsamen Teilers:
Finde den größten gemeinsamen Teiler von $412$ und $36$.
- $412:36 = 11$ Rest $16$
- $36:16 = 2$ Rest $4$
- $16:4 = 4$ Rest $0$
LösungHier berechnest du den größten gemeinsamen Teiler von $246$ und $48$ mit Hilfe der Division:
1. Schritt: Dividiere $246:48=5$ mit einem Rest von $246-5\cdot 48=246-240=6$.
2. Schritt: Teile nun den Divisor ($48$) durch den Rest ($6$). Du erhältst $48:6=8$ Rest $0$.
Du bist bereits fertig, da der Rest $0$ ist. Der letzte Divisor ist der gesuchte größte gemeinsame Teiler:
ggT$(48;246)=6$.
-
Gib die Summenregel für die Teilbarkeit an.
TippsPrüfe jede der obigen Aussagen an dem gegebenen Beispiel. Ist die Aussage für dieses Beispiel falsch, so kann die Aussage auch im Allgemeinen nicht gelten.
Du kannst $21$ nicht ohne Rest durch $14$ dividieren.
Es ist $7\cdot 7=49$ sowie $13\cdot 7=91$.
- $70-21 =49$ und
- $70+21=91$
LösungDie Zahl $7$ teilt sowohl $21$ also auch $70$. Sie ist also ein gemeinsamer Teiler. Es gilt die Summenregel. Diese besagt:
Wenn zwei Zahlen einen gemeinsamen Teiler haben, dann teilt dieser gemeinsame Teiler auch die Summe sowie die Differenz der beiden Zahlen.
Übrigens: Der gemeinsame Teiler teilt natürlich auch das Produkt, aber im Allgemeinen nicht den Quotienten der beiden Zahlen.
Schauen wir uns das Beispiel an:
- Die Summe der beiden Zahlen ist $70+21=91$ und es gilt $7\mid 91$, da $13\cdot 7=91$ ist.
- Das Doppelte von $7$ ist $14$ und $14$ teilt $21$ nicht.
- Der Quotient der beiden Zahlen ist $\frac{70}{21} = 3{,}\overline{3}$. Da dies keine natürliche Zahl ist, hat diese Zahl keine Teiler.
- Die Differenz der beiden Zahlen ist $70-21 =49$ und es gilt $7\mid 49$, da $7\cdot 7=49$ ist.
-
Vergleiche die beiden euklidischen Algorithmen.
TippsDer euklidische Algorithmus mit Subtraktion beginnt so:
- $702-318=384$
- $384-318=66$
- $318-66=252$
Der Euklidische Algorithmus mit Division beginnt so:
- $702:318=2$ Rest $66$
- $318:66=4$ Rest $54$
Bei dem euklidischen Algorithmus Subtraktion werden $7$ Rechnungen mehr durchgeführt als bei dem mit der Division.
LösungIst das Bestimmen des größten gemeinsamen Teilers mit Hilfe der Subtraktion tatsächlich so viel aufwendiger als mit der Division? Das überprüfen wir nun einmal an einem Beispiel. Es soll ggT$(318;702)$ bestimmt werden.
Beginne mit der Subtraktion. Du rechnest so lange, bis Subtrahend und Differenz in einer Rechnung übereinstimmen. Das ist dann der gesuchte größte gemeinsame Teiler.
- $702-318=384$
- $384-318=66$
- $318-66=252$
- $252-66=186$
- $186-66=120$
- $120-66=54$
- $66-54=12$
- $54-12=42$
- $42-12=30$
- $30-12=18$
- $18-12=6$
- $12-6=6$
Na, mal schauen, ob das mit der Division schneller geht:
- $702:318=2$ Rest $66$
- $318-66=4$ Rest $54$
- $66:54=1$ Rest $12$
- $55:12=4$ Rest $6$
- $12:6=2$ Rest $0$
Der erste Algorithmus braucht also mehr Schritte. Vielleicht fällt er dir dennoch leichter? Rechne einige weitere Aufgaben und entscheide für dich, welchen Algorithmus du lieber benutzt.
8.883
sofaheld-Level
6.601
vorgefertigte
Vokabeln
7.851
Lernvideos
37.611
Übungen
33.728
Arbeitsblätter
24h
Hilfe von Lehrkräften
Inhalte für alle Fächer und Klassenstufen.
Von Expert*innen erstellt und angepasst an die Lehrpläne der Bundesländer.
Testphase jederzeit online beenden
Beliebteste Themen in Mathematik
- Römische Zahlen
- Prozentrechnung
- Primzahlen
- Geometrische Lagebeziehungen
- Was ist eine Ecke?
- Rechteck
- Was ist eine Gleichung?
- Pq-Formel
- Binomische Formeln
- Trapez
- Volumen Zylinder
- Umfang Kreis
- Quadrat
- Division
- Raute
- Parallelogramm
- Polynomdivision
- Was Ist Eine Viertelstunde
- Prisma
- Mitternachtsformel
- Äquivalenzumformung
- Grundrechenarten Begriffe
- Größer Kleiner Zeichen
- Dreiecksarten
- Aufbau von Dreiecken
- Quader
- Satz Des Pythagoras
- Dreieck Grundschule
- Erste Binomische Formel
- Kreis
- Trigonometrie
- Trigonometrische Funktionen
- Standardabweichung
- Flächeninhalt
- Volumen Kugel
- Zahlen In Worten Schreiben
- Meter
- Orthogonalität
- Schriftlich Multiplizieren
- Brüche gleichnamig machen
- Brüche Multiplizieren
- Potenzgesetze
- Distributivgesetz
- Flächeninhalt Dreieck
- Rationale Zahlen
- Volumen Berechnen
- Brüche Addieren
- Kongruenz
- Exponentialfunktion
- Exponentialfunktion Beispiel
voll gut
Nice
Eukulid war meine erste Briefmarke bei der lernsafari
Super Video! Versteh nicht warum das nur 3,5 Sternchen hat! Ich habs selber ausgerechnet mit den Zahlen 235 und 721, aber die sind teilerfremd. Das war mit - . Geteilt hab ich mit den Zahlen 214 und 102, und deren ggT ist 2. Nicht so spektakulär😁
cool