Select your language

Suggested languages for you:
Log In Anmelden
StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
|
|

Die All-in-one Lernapp:

  • Karteikarten
  • NotizenNotes
  • ErklärungenExplanations
  • Lernpläne
  • Übungen
App nutzen

Euklidischer Algorithmus

Save Speichern
Print Drucken
Edit Bearbeiten
Melde dich an und nutze alle Funktionen. Jetzt anmelden
Euklidischer Algorithmus

Es steht Dein Geburtstag vor der Tür und Du hast unter anderem am Nachmittag vor, ein paar Verwandte und Deine Freundinnen und Freunde einzuladen. Was darf bei solch einer Party natürlich nicht fehlen? Eine Geburtstagstorte, die Du schon zuvor portionieren möchtest, damit Deine Gäste einfach nur zugreifen können. Dazu hast Du Dir von Deinem Nachbarn zwei Tortenteiler geliehen, mit deren Hilfe Du perfekte Stücke markieren kannst.

Der Euklidische Algorithmus Geburtstagskuchen StudySmarter

Dabei sind es zwei Zahlen, die für Dich interessant sind. Es handelt sich nämlich um 12 und 16 Kuchenstücke, in die Du Deinen Kuchen aufteilen könntest. Für jede Aufteilung kann dann wiederum eine Person zum Beispiel ein Stück essen, bzw. 3 Stücke für die Portionierung mit 12, zumindest wenn es auch durch diese Zahl ohne Rest geteilt werden soll. Wenn Du nun beide vergleichst, kommst Du in eine mathematische Berechnung für den größten gemeinsamen Teiler. Diesen hast Du eventuell bereits in der Schule gehört und Du kannst ihn über viele Wege berechnen. Einer davon ist der euklidische Algorithmus, über den Du in diesem Artikel mehr erfahren kannst.

Euklidischer Algorithmus – Grundlagenwissen

Um sich grundlegend mit dem euklidischen Algorithmus zu beschäftigen, sind für Dich noch ein paar Informationen wichtig, die Dir bei diesem Thema helfen. Zum einen ist das schriftliche Dividieren eine Voraussetzung. Allerdings fragst Du Dich auch, was der größte gemeinsame Teiler ist.

Euklidischer Algorithmus – Rechnen mit ganzen Zahlen

Die Berechnung mit ganzen Zahlen ist in diesem Artikel eine wichtige Voraussetzung. Dabei kennst Du die Addition, wie auch die Subtraktion. Ein anderes Beispiel aus der Arithmetik, also dem Berechnen von Zahlen, ist die Multiplikation. Vor allem dabei ist entscheidend, welches Vorzeichen der jeweilige Faktor besitzt. Dabei unterscheidest Du die Fälle, dass das Ergebnis...

  • positiv ist, wenn die Faktoren beide dasselbe Vorzeichen besitzen.
  • negativ ist, wenn die Faktoren unterschiedliche Vorzeichen besitzen.

In diesem Beispiel sind die Faktoren beide identisch:

Und hier wird ein negatives Produkt entstehen:

Dieses Beispiel zu den Vorzeichen gilt für die Division ebenso. Besitzen Dividend und Divisor dasselbe Vorzeichen, führt die Division zu einem positiven Ergebnis, ansonsten zu einem negativen.

Der Aufbau einer Division ist in folgender Grafik angegeben:

Möchtest Du noch einmal alles zu der Berechnung mit ganzen Zahlen lernen und vor allem auch, wie Du eine Division mit Rest durchführen kannst, sieh Dir dazu gerne die dazugehörigen Artikel an.

Euklidischer Algorithmus – Primfaktorzerlegung

Alle natürlichen Zahlen sind als ein Produkt von Primzahlen darstellbar bzw. Du kannst sie in ihre einzelnen Primfaktoren zerlegen. Dabei handelt es sich um eine Primzahl, wenn die einzigen Teiler die Zahl selbst und die eins sind.

Die Zahl 60 lässt sich zum Beispiel als Primfaktorzerlegung darstellen. Dabei probierst Du Schritt für Schritt aus, durch welche Primzahl sie jeweils ohne Rest geteilt werden kann. Du probierst am Besten relativ kleine Zahlen aus:

Dabei sind die Primfaktoren jeweils die Zahlen, durch die Du geteilt hast. Somit ist die Primfaktorzerlegung der Zahl 60 im Folgenden:

Die Reihenfolge, wie Du die Zahlen anordnest, ist dabei irrelevant. In der Standardform sind allerdings die Zahlen aufsteigend sortiert.

Euklidischer Algorithmus – ggT

Der Begriff des ggT ist für diesen Artikel sehr zentral, da der euklidische Algorithmus ein Verfahren zur Bestimmung des ggT ist.

Als größter gemeinsamer Teiler (ggT) wird die Zahl bezeichnet, die der größte Teiler von zwei oder mehreren Zahlen ist. Der größte gemeinsame Teiler lässt sich für zwei Zahlen a und b wie folgt beschreiben:

Euklidischer Algorithmus ggT für zwei Zahlen a und b StudySmarter

Formulieren lässt sich der größte gemeinsame Teiler als ggT von a und b. An dieser Stelle wäre es auch interessant, das Beispiel Deiner Geburtstagsparty zu verwenden.

Du hast also für Deine Geburtstagstorten zwei Tortenteiler mit 12 und 16 Sektoren erhalten. Möchtest Du nun wissen, welche Teiler für die jeweiligen Zahlen infrage kommen, schreibst Du diese auf:

In diesem Beispiel ist Dir bereits markiert worden, welche der größte Teiler ist, der für beide Zahlen vorkommt. Es gilt also:

Diese Aufstellung wie in dem gezeigten Beispiel ist allerdings nur für kleine Zahlen zu empfehlen. Werden sie größer, sollten andere Methoden verwendet werden. Dazu zählt der euklidische Algorithmus.

Euklidischer Algorithmus – Eigenschaften

Ein Instrument, um den größten gemeinsamen Teiler zu ermitteln, ist die Verwendung des euklidischen Algorithmus. Diesen und auch die weitere Form des erweiterten euklidischen Algorithmus wirst Du im Artikel lernen.

Euklidischer Algorithmus – Definition

Zu Beginn soll Dir eine kleine Definition einen Einblick verschaffen, worum es sich dabei handelt.

Der euklidische Algorithmus ist ein Verfahren zur Berechnung des größten gemeinsamen Teilers. Dabei wird eine Division mit Rest durchgeführt, mit Wechsel des Dividenden und Divisors für jeden Schritt.

Ein Algorithmus ist dabei eine klare und endliche Vorschrift eines Verhaltens oder einer Rechenoperation. Es handelt sich um eine Berechnung in der Arithmetik.

Der euklidische Algorithmus wurde hierbei - wie der Name vermuten lässt - vom griechischen Mathematiker Euklid entdeckt, wobei seine Leistungen im Bereich der Arithmetik und Geometrie bis hin zur Astronomie lagen. Der im vierten Jahrhundert vor Christus in Athen geborene Euklid wurde vor allem durch sein Buch "Die Elemente", mit dem Text über mathematische Erkenntnisse seiner Zeit berühmt.

Euklidischer Algorithmus – Vorgehen

Wie bereits erwähnt, handelt es sich beim euklidischen Algorithmus um das Verfahren, das durch die Division mit Rest den größten gemeinsamen Teiler ermittelt. Er ist allerdings nur für zwei Zahlen anwendbar, im Unterschied zur Bestimmung des ggT über die Primfaktorzerlegung.

Dabei wird grundsätzlich eine Division der größeren durch die kleinere Zahl mit Rest stattfinden.

Eine sehr kurze Antwort darauf, wie der euklidische Algorithmus funktioniert, ist hiermit gegeben:

  1. Größere Zahl durch kleinere dividieren
  2. Den Divisor durch den Rest dividieren.
  3. Solange durchführen, bis kein Rest mehr vorhanden ist. Dann Ergebnis aufschreiben.

Etwas präziser formuliert wird Dir der euklidische Algorithmus in diesem Fall:

  1. Du hast eine größere Zahl a und eine kleinere Zahl b gegeben.
  2. Du teilst nun die größere Zahl a durch die Zahl b. Falls dabei kein Rest herauskommt, ist die Zahl b bereits Dein ggT.
  3. Falls ein Rest übrig bleibt, gehst Du wie folgt vor: Für die nächste Rechnung nutzt Du Dein b als alten Divisor nun als Dividend und den Rest als Divisor. Du teilst im nächsten Schritt also den Wert des alten b durch den Rest.
  4. Dieses Verfahren wendest Du so lange an bis kein Rest mehr herauskommt.
  5. Der Divisor dieser Rechnung ist dann Dein ggT.

Es kann dabei durchaus helfen, sich dieses Verfahren des Algorithmus aus der Arithmetik bildlich vorzustellen:

Berechnung des ggT für 3 Zeilen:

Es gilt:

  • a ist größere Zahl bzw. Dividend.
  • b ist kleinere Zahl bzw. Divisor.
  • Euklidischer Algorithmus Faktor für Division StudySmarter steht für den Faktor, wie oft der Divisor in den Dividend passt.
  • Euklidischer Algorithmus Rest der Division des ggT StudySmarter ist der Rest der Division.

Euklidischer Algorithmus Berechnung des ggT für 2 Zeilen StudySmarter

Die Beendigung des Algorithmus, wenn kein Rest mehr vorhanden ist, wird wie folgt formuliert:

Euklidischer Algorithmus Berechnung des ggT allgemein StudySmarter

Nun hast Du bereits allgemein und theoretisch erfahren, wie der euklidische Algorithmus anzuwenden ist. An dieser Stelle wäre doch ein Beispiel recht.

Dieses Beispiel soll Dir Schritt für Schritt anhand Deiner Geburtstagsparty helfen, das Konzept des Artikels zu verinnerlichen. Führe also den euklidischen Algorithmus für 12 und 16 durch. Dabei wird eine Tabelle verwendet.

abqr
16:12=1Rest4
12:4=3Rest 0

Hier noch einmal eine Erwähnung, welcher Schritt auf den anderen folgt, um den Algorithmus zu bestimmen.

Die Zahl a muss die größere der beiden sein, also die 16. Auch hier gilt a für den Dividend, b für den Divisor, für den Faktor, wie oft a in b hineinpasst und für den Rest der Division.

Für die erste Zeile gilt:

Für die zweite Zeile:

Gibt es also eine Division, bei der der Rest 0 ergibt, so benötigst Du keine weitere Division und Du kannst den Divisor als ggT ausgeben. In diesem Fall ist es die Zahl 4.

Den Algorithmus kannst Du also nun anwenden. Ein weiteres Übungsbeispiel und Aufgaben dazu wirst Du später noch finden.

Über die Ermittlung des ggT für zwei Zahlen a und b durch die Division mit Rest, kannst Du daraufhin in einem zweiten Schritt das kleinste gemeinsame Vielfache (kgV) bestimmen. Das kgV ist nämlich der Quotient aus dem Produkt der Zahlen a und b mit seinem ggT. Beispielsweise ermittelt sich für und das kgV folgendermaßen:

Euklidischer Algorithmus – Beweis

Wenn Du in Erfahrung bringen möchtest, ob der euklidische Algorithmus korrekt ist, so kannst Du Dir den gemeinsamen Teiler d von zwei Zahlen a und b ansehen. a und b sind Teil der natürlichen Zahlen, a auch zusätzlich mit der 0. Die Zahl d ist der ggT von a und b, also:

Die Zahl d ist also die Zahl, die sowohl a als auch b teilt.

Es gilt aber nicht nur die Division mit Rest von a und b, sondern auch die Differenz von a und b. Dies war ursprünglich auch der euklidische Algorithmus.

Der Modulo () zweier Zahlen ist dabei die Division mit Rest, wobei dieser Rest das Ergebnis darstellt.

Diese Zeile bedeutet sozusagen, dass die Division von a und b mit Rest - was Du im vorherigen Kapitel durchgeführt hast - identisch zu der Differenz von a und b ist. Dabei steht q für eine ganzzahlige Division von a und b. Das lässt sich am besten am Beispiel aus der Einleitung zeigen.

Auch hier gilt, dass a = 16 und b = 12 ist.

Dasselbe gilt für die Differenz:

Diese Rechnung ist nur exemplarisch für einen Durchgang. Der zweite wurde ausgespart. Es wird im nächsten Schritt allerdings herauskommen, dass beide den Rest 0 besitzen.

Für den größten gemeinsamen Teiler von 16 und 0 gilt, dass der ggT 16 ist, also:

Erweiterter Euklidischer Algorithmus

Der erweiterte euklidische Algorithmus ist eine Erweiterung der Division zweier Zahlen, um noch eine zusätzliche Information zu erhalten. Über diesen wirst Du im folgenden Kapitel mehr erfahren.

Erweiterter Euklidischer Algorithmus – Definition

Der erweiterte euklidische Algorithmus ist eine Erweiterung des euklidischen Algorithmus des Mathematikers Bézout. Es wird auch als Lemma von Bézout bezeichnet.

Der erweiterte euklidische Algorithmus ermittelt eine Linearkombination des ggT für die Zahlen a und b. Dabei beschreibt eine Linearkombination die Verknüpfung eines Vektors, der mit einer Zahl multipliziert wird, mit einem anderen Vektor. Dieser Vorgang der Addition mehrerer Vektoren kann mehrfach stattfinden. Zu den natürlichen Zahlen a und b, die in diesem Fall aber nicht 0 sein dürfen, können zusätzlich die Buchstaben s und t berechnet werden.

Euklidischer Algorithmus Erweiterter Euklidischer Algorithmus StudySmarter

Der erweiterte euklidische Algorithmus ist also der euklidische Algorithmus, bei dem von der letzten Zeile nach oben, bzw. rückwärts der jeweilige Rest aufgelöst und immer weiter eingesetzt wird.

Erweiterter euklidischer Algorithmus – Tabelle

Es gibt grundsätzlich zwei Formen, wie Du diese Aufgabe angehen kannst. Für diesen Fall aus der Arithmetik soll der größte gemeinsame Teiler und seine Linearkombination von zwei Zahlen in Tabellenform gelöst werden.

Dabei gehst Du wie folgt vor:

  1. Löse den erweiterten euklidischen Algorithmus wie im vorherigen Kapitel besprochen.
  2. Wenn sich der Rest 0 ergibt, setzt Du für den Buchstaben s die Zahl 0 und für t die Zahl 1 ein.
  3. Nun gehst Du die Tabelle von unten nach oben durch. Dabei fügst Du in jeder Zeile für s den Wert von t aus der vorherigen Zeile ein. Dieses t berechnest Du über eine Formel.

Die Formel zur Berechnung von t beim "Rückwärtsgehen" für jeden Schritt ist:

Falls Du noch Schwierigkeiten hast, das zu lösen, dann nutze doch gerne dieses Beispiel, mit dem Du Schritt für Schritt vorgehen kannst.

Berechne den größten gemeinsamen Teiler und die Linearkombination für .

Dazu nutzt Du eine Tabelle. In diesem Fall werden bewusst zwei Tabellen verwendet, damit jeder Schritt ersichtlich ist. In dieser Tabelle sind keine Rechenzeichen mehr gegeben. Dabei ist hier die Division von a und b mit Rest weiterhin das Vorgehen.

nabqr
1512501012
2501242
312260

Nun hast Du also den Rest 0 ermittelt. Der größte gemeinsame Teiler von 512 und 50 ist also 2.

Nun erweiterst Du diese Tabelle um die Buchstaben s und t und fügst ein: s = 0, t = 1.

Denk daran, hier in der letzten Zeile zu beginnen.

Danach verwendest Du die Formel.

nabqrst
1512501012-441
25012421-4
31226001
  1. Im ersten Schritt fügst Du also für s und t die Zahlen 0 und 1 ein.
  2. Im zweiten Schritt und bis die Tabelle ausgefüllt ist, soll s die Zahl des alten t bekommen und t über die Formel berechnet werden.
  3. Wenn nichts mehr auszufüllen ist, sind die Zahlen für s und t die gesuchten Werte.

Um die nächste Zeile, also zu berechnen, gehst Du so vor:

  1. s bekommt den alten Wert von t, also die 1.
  2. t ermittelst Du über die Formel:

Um sicher zu gehen, dass Deine Rechnung und die Bearbeitung des Algorithmus für die Zahlen a und b richtig war, kannst Du die Linearkombination berechnen und Du erhältst den ggT.

Der ggT von a und b ist tatsächlich 2. Das hattest Du zuvor ermittelt.

Euklidischer Algorithmus – rückwärts

Ein weiteres Verfahren, bei dem Du keine Tabelle benötigst, ist das Verfahren, in dem sukzessive rückwärts eingesetzt wird. Auch in diesem Beispiel nutzt Du den euklidischen Algorithmus und führst die Division Schritt für Schritt durch. Statt eine Tabelle zu zeichnen, kannst Du nun rückwärts einsetzen.

Nutze den erweiterten euklidischen Algorithmus für die folgenden Zahlen. Verwende zur Berechnung der Linearkombination allerdings das Verfahren zum rückwärtigen Einsetzen.

Zunächst nutzt Du den euklidischen Algorithmus. Es spricht natürlich nichts dagegen, diesen in Tabellenform auszurechnen. Da allerdings die große Tabelle für s und t nicht verwendet wird, soll der Algorithmus in diesem Beispiel multiplikativ ausgedrückt werden.

Der euklidische Algorithmus lässt sich über diese Formel berechnen:

Also kannst Du die Formel verwenden, um den ggT zu ermitteln. Beachte dabei auch die farblichen Markierungen.

Nun hast Du also bereits den ggT der Zahlen 157 und 11 bestimmen können. Es ist die Zahl 1. Nun nutzt Du den ggT auf der einen Seite Deiner Gleichung und auf der anderen die Rechnung der Zeile darüber, allerdings ohne den Rest.

Die Rechnung der Zeile darüber musst Du noch auf eine Seite bringen, also gleich 0 setzen, damit Du sie mit dem ggT gleichsetzen kannst.

Für dieses Beispiel nutzt Du also die vorletzte Zeile. Die letzte Zeile ist grundsätzlich uninteressant, da Du für die Vollständigkeit angibst, wie oft b in Dein neues a hineinpasst. Du subtrahierst b und q aus der vorletzten Zeile. Die Berechnung funktioniert also wie folgt:

Für die Berechnung fehlt allerdings noch eine Zeile. Du nutzt also den ermittelten ggT und

  1. fügst die obere Zeile ohne den Rest ein.
  2. in der zweiten Zeile fügst Du für Dein b den Schritt darüber ein, auch hier wieder ohne Rest.

Dieses Verfahren führst Du so lange durch, bis Du an der ersten Zeile angelangt bist, also:

Noch zusammen gerechnet erhältst Du die Lösung

Erweiterter euklidischer Algorithmus – Polynome

Nun kann der euklidische Algorithmus und seine Division mit Rest nicht nur für zwei Zahlen gegeben sein, sondern auch für ein Polynom. Dabei wird jeweils eine Polynomdivision durchgeführt. Im nächsten Schritt wird das Ergebnis aus der Rechnung als Dividend und der Rest als Divisor der nächsten Polynomdivision verwendet, bis der Rest 0 heraus kommt.

Falls Du allerdings zuvor eine Wiederholung der Polynomdivision benötigst und Dich mit der Arithmetik beschäftigen möchtest, ist es durchaus sinnvoll, den Text zur Polynomdivision anzusehen. Dort wird Dir das Vorgehen erläutert.

Nun sollst Du anhand der Polynomdivision in mehreren Schritten in diesem Teil im Artikel erfahren, wie Du konkret vorgehen kannst.

Gegeben sind die Polynome f und g. Du kannst nun den ggT beider Polynome bestimmen.

Schritt 1:

Schritt 2:

Im nächsten Schritt verwendest Du das Ergebnis deiner Polynomdivision und den Rest, um eine weitere durchzuführen.

Schritt 3:

Da dabei noch nicht der Rest 0 herausgekommen ist, soll die Polynomdivision noch einmal durchgeführt werden. Das kann im schlimmsten Fall n-mal vorkommen, ist allerdings für Dich nicht relevant, wenn Du händisch ein Ergebnis erzielen sollst.

Schritt 4:

Der ggT der Polynome f und g ist dabei:

Euklidischer Algorithmus - Aufgaben

Nachdem Du bereits einige Anwendungen zum euklidischen Algorithmus gesehen hast, sollst Du jetzt die Möglichkeit haben, Dich damit noch ein klein wenig praktisch zu beschäftigen.+

Aufgabe 1

Was ist der größte gemeinsame Teiler für die folgenden Zahlen: ?

´

  1. Bestimme den ggT, indem Du die Primfaktorzerlegung anwendest.
  2. Erkläre den Begriff des ggT.
  3. Berechne den ggT über den euklidischen Algorithmus.

Lösung

a. Grundsätzlich kannst Du auch die Teiler der beiden Zahlen bestimmen und den größten markieren, der in beiden vorkommt. Allerdings haben die Zahlen viele Teiler, weshalb sich die Primfaktorzerlegung anbietet. Für a soll Dir die Lösung Schritt für Schritt angegeben sein.

Die Primfaktorzerlegung ergibt also folgendes. Dabei soll Dir auch bereits die Primfaktorzerlegung für 140 angegeben sein. Alle Zahlen, die für beide identisch sind, sind hierbei farblich markiert:

Nun sind nur noch die Zahlen zu multiplizieren:

b. Der ggT wird als größter gemeinsamer Teiler bezeichnet und ist der größte Teiler, der sowohl die Zahl a als auch die Zahl b teilt. Er ist über die Primfaktorzerlegung, aber auch über die Aufschlüsselung der Teiler, bzw. über den euklidischen Algorithmus und die Division mit Rest zu bestimmen.

c. Für die Lösung des euklidischen Algorithmus wird Dir die Tabellenform angegeben:

abqr
2401401100
140100140
10040220
402020

In der letzten Zeile ist der Rest 0 gegeben. Deshalb nutzt Du die Zahl in der Spalte von b. Dabei erhältst Du auch, dass der größte gemeinsame Teiler zu 140 und 240 die Zahl 20 ist.

Aufgabe 2

Gegeben sind Dir folgende Zahlen: .

  1. Bestimme den ggT. Bitte nicht in Tabellenform.
  2. Bestimme die Linearkombination.

Lösung

a. Dafür soll a die größere der beiden Zahlen sein. Somit gilt b = 450. Die Lösung soll dabei nicht über die Tabelle und die Schreibweise der Division sein, sondern die Multiplikation, so wie Dir am Anfang gezeigt. Der Grund dafür ist, dass Du auch diese Schreibweise üben sollst.

b. Ermittle nun die Linearkombination. Dies wird in Tabellenform erledigt. Nur die farbig markierten Zahlen sind nun neu. Dabei...

  • fügst Du die Zahlen 0 und 1 für s und t ein.
  • Danach erhält s das alte t und
  • t berechnet sich über die Formel:

nabqrst
1387045082702-17
24502701180-12
32701801901-1
4180902001

Die Linearkombination ist also:

Aufgabe 3

Gegeben sind Dir folgende Polynome:

Ermittle den größten gemeinsamen Teiler über die Berechnung durch die Polynomdivision.

Tipp: Es ist nur eine Polynomdivision nötig.

Lösung

Der ggT ist also:

Euklidischer Algorithmus – Das Wichtigste

  • Die Division besteht aus dem Dividend und dem Divisor. Das Ergebnis ist dabei der Wert des Quotienten.
  • Du kannst jede Zahl in ihre Primzahlen aufteilen und damit den größten gemeinsamen Teiler bestimmen.
  • Der ggT ist der größte Teiler zweier oder mehrerer Zahlen, wobei er unter anderem durch die Primfaktorzerlegung oder den euklidischen Algorithmus ermittelt werden kann.
  • Der euklidische Algorithmus besteht darin, eine Division zweier Zahlen mit Rest durchzuführen bis der Rest 0 als Ergebnis steht. Dabei wechselt der Divisor und der Rest vom vorherigen Schritt zum Dividend und Divisor im nächsten.
  • Der erweiterte euklidische Algorithmus kann die Linearkombination zweier Zahlen ermitteln und wird wie folgt angegeben:
  • Für die Tabellenform kannst Du nach der Berechnung des ggT und dem Einsetzen der Zahlen 0 und 1 für s und t im darauffolgenden Schritt den alten Wert von t für s und für t die Formel verwenden.
  • Auch für Polynome sind Polynomdivisionen so oft durchzuführen, bis der Rest 0 angegeben ist.

Häufig gestellte Fragen zum Thema Euklidischer Algorithmus

Der Euklidische Algortihmus ist in der modernen Form eine Division mit Rest. Dabei wird die Zahl a durch die Zahl b geteilt, wobei ein Rest entsteht. Der Divisor der ersten Rechnung wird der Dividend und der Rest zum Divisor der zweiten Rechnung. Sobald der Rest den Wert 0 annimmt, ist mit der Zahl b der größte gemeinsame Teiler gefunden.

Der erweiterte euklidische Algorithmus ermittelt zu dem ggT zweier Zahlen zusätzlich die Linearkombination. Dabei werden zusätzlich die Zahlen s und t über das rückwärtige Einsetzen, bzw. in Tabellenform ermittelt.

Den größten gemeinsamen Teiler kannst Du über die Primfaktorzerlegung zweier oder mehrerer Zahlen ermitteln. Außerdem kannst Du für jede Zahl Teiler aufstellen. Der größte Teiler, den jede Zahl beinhaltet ist der ggT. Du kannst den größten gemeinsamen Teiler aber auch über den euklidischen Algorithmus berechnen.

Der größte gemeinsame Teiler zweier Primzahlen ist 1, da jede Primzahl nur durch sich selbst und 1 teilbar ist.

Finales Euklidischer Algorithmus Quiz

Frage

Erkläre kurz den Begriff Division, Dividend und Divisor.

Antwort anzeigen

Antwort

Der Dividend ist die Zahl, die durch den Divisor geteilt wird. Das bezeichnet man als Quotient. Zusammen mit dem Wert des Quotienten ist der ganze Ausdruck eine Division.

Frage anzeigen

Frage

Was ist der ggT zu 44 und 96?

Antwort anzeigen

Antwort

4

Frage anzeigen

Frage

Worin unterscheiden sich der euklidische und erweiterte euklidische Algorithmus?

Antwort anzeigen

Antwort

Der euklidische Algorithmus bestimmt den größten gemeinsamen Teiler von zwei Zahlen.

Der erweiterte euklidische Algorithmus bestimmt darüber hinaus die Linearkombination, die wiederum dem ggT entspricht.

Frage anzeigen

Frage

Welche Aussage über den euklidischen Algorithmus stimmt nicht?

Antwort anzeigen

Antwort

Zahl a wird von b subtrahiert.

Frage anzeigen

Frage

Was ist der ggT von 97 und 11?

Antwort anzeigen

Antwort

Da beide Primzahlen sind, können sie automatisch nur die 1 als ggT haben.

Frage anzeigen
Mehr zum Thema Euklidischer Algorithmus
60%

der Nutzer schaffen das Euklidischer Algorithmus Quiz nicht! Kannst du es schaffen?

Quiz starten

Finde passende Lernmaterialien für deine Fächer

Alles was du für deinen Lernerfolg brauchst - in einer App!

Lernplan

Sei rechtzeitig vorbereitet für deine Prüfungen.

Quizzes

Teste dein Wissen mit spielerischen Quizzes.

Karteikarten

Erstelle und finde Karteikarten in Rekordzeit.

Notizen

Erstelle die schönsten Notizen schneller als je zuvor.

Lern-Sets

Hab all deine Lermaterialien an einem Ort.

Dokumente

Lade unzählige Dokumente hoch und habe sie immer dabei.

Lern Statistiken

Kenne deine Schwächen und Stärken.

Wöchentliche

Ziele Setze dir individuelle Ziele und sammle Punkte.

Smart Reminders

Nie wieder prokrastinieren mit unseren Lernerinnerungen.

Trophäen

Sammle Punkte und erreiche neue Levels beim Lernen.

Magic Marker

Lass dir Karteikarten automatisch erstellen.

Smartes Formatieren

Erstelle die schönsten Lernmaterialien mit unseren Vorlagen.

Gerade angemeldet?

Ja
Nein, aber ich werde es gleich tun

Melde dich an für Notizen & Bearbeitung. 100% for free.