Euklidischer Algorithmus

Algebra

INHALTSANGABE :

INHALTSANGABE

Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken

Jetzt kostenlos anmelden

Nie wieder prokastinieren mit unseren Lernerinnerungen.

Jetzt kostenlos anmelden

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.

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:

$(- 6) \cdot (- 8) = 48$

Und hier wird ein negatives Produkt entstehen:

$6 \cdot (- 8) = - 48$

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:

$\overset{D i v i s i o n}{\overset{⏞}{\overset{Q u o t i e n t}{\overset{⏞}{\underset{D i v i d e n d}{\underset{⏟}{100}} : \underset{D i v i s o r}{\underset{⏟}{10}}}} = \underset{W e r t Q u o t i e n t}{\underset{⏟}{10}}}}$

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.

Addieren ganzer Zahlen
Subtrahieren ganzer Zahlen
Multiplizieren ganzer Zahlen
Dividieren ganzer Zahlen

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:

$\begin{array}{rcl} 60 : 2 & = & 30 \\ 30 : 2 & = & 15 \\ 15 : 3 & = & 5 \\ 5 : 5 & = & 1 \end{array}$

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

$60 = 2 \cdot 2 \cdot 3 \cdot 5$

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:

$g g T (a, b)$

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:

$\begin{array}{rcl} T (12) & = & {1, 2, 3, 4, 6, 12} \\ T (16) & = & {1, 2, 4, 8, 16} \end{array}$

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

$g g T (12, 16) = 4$

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:

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

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

Du hast eine größere Zahl a und eine kleinere Zahl b gegeben.
Du teilst nun die größere Zahl a durch die Zahl b. Falls dabei kein Rest herauskommt, ist die Zahl b bereits Dein ggT.
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.
Dieses Verfahren wendest Du so lange an bis kein Rest mehr herauskommt.
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.
$q_{n}$ steht für den Faktor, wie oft der Divisor in den Dividend passt.
$r_{n}$ ist der Rest der Division.

$\begin{array}{rcl} a & = & q_{1} \cdot b + r_{0} \\ b & = & q_{2} \cdot r_{0} + r_{1} \\ r_{0} & = & q_{3} \cdot r_{1} + r_{2} \end{array}$

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

$r_{n - 2} = z_{n + 1} \cdot r_{n - 1} + 0$

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.

$g g T (12, 16)$

a		b		q		r
16	:	12	=	1	Rest	4
12	:	4	=	3	Rest	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, $q_{1}$ für den Faktor, wie oft a in b hineinpasst und $r_{0}$ für den Rest der Division.

Für die erste Zeile gilt:

$\begin{array}{rcl} a & = & q_{1} \cdot b + r_{0} \\ 16 & = & 1 \cdot 12 + 4 \end{array}$

Für die zweite Zeile:

$\begin{array}{rcl} b & = & q_{2} \cdot r_{0} + r_{1} \\ 12 & = & 3 \cdot 4 + 0 \end{array}$

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 $a = 15$ und $b = 25$ das kgV folgendermaßen:

$\begin{array}{rcl} k g V (a, b) & = & (a \cdot b) : g g T (a, b) \\ = & (15 \cdot 25) : 5 \\ = & 75 \end{array}$

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:

$g g T (a, b) = d$

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

$d | a, b$

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.

$r = a m o d d = a - q \cdot b, w o b e i g i l t : q = a d i v b (g a n z z a h l i g) .$

Der Modulo ( $m o d$ ) 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.

$\begin{array}{rcl} r & = & a m o d b \\ 4 & = & 16 m o d 12 \\ 4 & = & 4 b z w . r = 4 \end{array}$

Dasselbe gilt für die Differenz:

$\begin{array}{rcl} r & = & a - q \cdot b \\ r & = & 16 - (16 : 12) \cdot 12 \\ 4 & = & 16 - 1 \cdot 12 \\ 4 & = & 4 b z w . r = 4 \end{array}$

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:

$g g T (a, 0) = a$

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.

$g g T (a, b) = s \cdot a + t \cdot b$

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:

Löse den erweiterten euklidischen Algorithmus wie im vorherigen Kapitel besprochen.
Wenn sich der Rest 0 ergibt, setzt Du für den Buchstaben s die Zahl 0 und für t die Zahl 1 ein.
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:

$t = s_{a l t} - q \cdot t_{a l t}$

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 $a = 512, b = 50$ .

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.

n	a	b	q	r
1	512	50	10	12
2	50	12	4	2
3	12	2	6	0

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.

n	a	b	q	r	s	t
1	512	50	10	12	-4	41
2	50	12	4	2	1	-4
3	12	2	6	0	0	1

Im ersten Schritt fügst Du also für s und t die Zahlen 0 und 1 ein.
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.
Wenn nichts mehr auszufüllen ist, sind die Zahlen für s und t die gesuchten Werte.

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

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

$t = s_{a l t} - q \cdot t_{a l t} = 1 - 4 \cdot 1 = - 4$

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.

$\begin{array}{rcl} g g T (512, 50) & = & a \cdot s + b \cdot t \\ g g T (512, 50) & = & 512 \cdot s + 50 \cdot t \\ g g T (512, 50) & = & 512 \cdot - 4 + 50 \cdot 41 \\ g g T (512, 50) & = & 2 \end{array}$

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.

$a = 157, b = 11$

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:

$r_{n - 2} = z_{n + 1} \cdot r_{n - 1} + 0$

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

$\begin{array}{rcl} 157 & = & 14 \cdot 11 + 3 \\ 11 & = & 3 \cdot 3 + 2 \\ 3 & = & 1 \cdot 2 + 1 \\ (2 & = & 2 \cdot 1) \end{array}$

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:

$\begin{array}{rcl} 1 & = & 3 - 1 \cdot 2 \\ 1 & = & 3 - 1 \cdot (11 - 3 \cdot 3) \end{array}$

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

fügst die obere Zeile ohne den Rest ein.
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:

$\begin{array}{rcl} 1 & = & 3 - 1 \cdot 2 \\ 1 & = & 3 - 1 \cdot (11 - 3 \cdot 3) = - 1 \cdot 11 + 4 \cdot 3 \\ 1 & = & - 1 \cdot 11 + 4 \cdot (157 - 14 \cdot 11) \end{array}$

Noch zusammen gerechnet erhältst Du die Lösung

$g g T (157, 11) = 4 \cdot 157 - 57 \cdot 11 = 1$

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.

$f (x) = x^{5} + x^{4} + x^{3} + x^{2} + x + 1$
$g (x) = x^{4} - x^{3} - x + 1$

Schritt 1:

$(x^{5} + x^{4} + x^{3} + x^{2} + x + 1) = (x^{4} - x^{3} - x + 1) \cdot (x + 2), R e s t 3 x^{3} + 2 x^{2} + 2 x - 1 - (x^{5} - x^{4} - x^{2} + x)___________________2 x^{4} + x^{3} + 2 x^{2} + 1 - (2 x^{4} - 2 x^{3} - 2 x + 2)_____________________3 x^{3} + 2 x^{2} + 2 x - 1$

Schritt 2:

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

$x^{4} - x^{3} - x + 1 = (3 x^{3} + 2 x^{2} + 2 x - 1) \cdot (\frac{1}{3} x + \frac{5}{9}), R e s t \frac{4}{9} (x^{2} + x + 1) - (x^{4} + \frac{2}{3} x^{3} + \frac{2}{3} x^{3} - \frac{1}{3} x)_____________________- \frac{5}{3} x^{3} - \frac{2}{3} x^{2} - \frac{2}{3} x + 1 - (- \frac{5}{3} x^{3} - \frac{10}{9} x^{2} - \frac{10}{9} + \frac{5}{9})____________________________\frac{4}{9} x^{2} + \frac{4}{9} x + \frac{4}{9}$

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.

$\begin{array}{rcl} 3 x^{3} + 2 x^{2} + 2 x - 1 = (x^{2} + x + 1) \cdot (3 x - 1), R e s t 0 \end{array} - (3 x^{3} + 3 x^{2} + 3 x)________________- x^{2} - x - 1 - (- x^{2} - x - 1)________________0$

Schritt 4:

Der ggT der Polynome f und g ist dabei:

$g g T (f, g) = x^{2} + x + 1$

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: $a = 240, b = 140$ ?

Bestimme den ggT, indem Du die Primfaktorzerlegung anwendest.
Erkläre den Begriff des ggT.
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.

$\begin{array}{rcl} 240 : 2 & = & 120 \\ 120 : 2 & = & 60 \\ 60 : 2 & = & 30 \\ 30 : 2 & = & 15 \\ 15 : 3 & = & 5 \\ 5 : 5 & = & 0 \end{array}$

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:

$\begin{array}{rcl} 240 & = & 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 5 \\ 140 & = & 2 \cdot 2 \cdot 5 \cdot 7 \end{array}$

Nun sind nur noch die Zahlen zu multiplizieren:

$\begin{array}{rcl} 2 \cdot 2 \cdot 5 & = & 20 \\ g g T (240, 140) & = & 20 \end{array}$

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:

a	b	q	r
240	140	1	100
140	100	1	40
100	40	2	20
40	20	2	0

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: $450, 3870$ .

Bestimme den ggT. Bitte nicht in Tabellenform.
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.

$\begin{array}{rcl} 3870 & = & 8 \cdot 450 + 270 \\ 450 & = & 1 \cdot 270 + 180 \\ 270 & = & 1 \cdot 180 + 90 \\ 180 & = & 2 \cdot 90 + 0 \end{array}$

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:

$t = s_{a l t} - q \cdot t_{a l t}$

n	a	b	q	r	s	t
1	3870	450	8	270	2	-17
2	450	270	1	180	-1	2
3	270	180	1	90	1	-1
4	180	90	2	0	0	1

Die Linearkombination ist also:

$\begin{array}{rcl} g g T (3870, 450) & = & 2 \cdot 3780 - 17 \cdot 450 = - 90 b z w . 90 \end{array}$

Aufgabe 3

Gegeben sind Dir folgende Polynome:

$\begin{array}{rcl} f (x) & = & x^{4} + 3 x^{3} + 5 x^{2} - x^{1} - 48 \end{array}$

$\begin{array}{rcl} g (x) & = & x + 3 \end{array}$

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

Tipp: Es ist nur eine Polynomdivision nötig.

Lösung

$(x^{4} + 3 x^{3} + 5 x^{2} - x - 48) : (x + 3) = x^{3} + 5 x - 16 - (x^{4} + 3 x^{3})_________0 + 5 x^{2} - x - (5 x^{2} + 15 x)___________- 16 x - 48 - (- 16 x - 48)____________0$

Der ggT ist also:

$x^{3} + 5 x - 16$

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: $g g T (a, b) = s \cdot a + t \cdot b$
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 $t = s_{a l t} - q \cdot t_{a l t}$ 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.

Karteikarten in Euklidischer Algorithmus5 Lerne jetzt

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

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.

Was ist der ggT zu 44 und 96?

Worin unterscheiden sich der euklidische und erweiterte euklidische Algorithmus?

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.

Welche Aussage über den euklidischen Algorithmus stimmt nicht?

Zahl a wird von b subtrahiert.

Was ist der ggT von 97 und 11?

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

Lerne mit 5 Euklidischer Algorithmus Karteikarten in der kostenlosen StudySmarter App

Mit E-Mail registrieren ANMELDEN ANMELDEN

Du hast bereits ein Konto? Anmelden

Finde Lernmaterialien und -tipps

Erstelle Lernmaterialien

Blog

Euklidischer Algorithmus

Euklidischer Algorithmus – Grundlagenwissen

Euklidischer Algorithmus – Rechnen mit ganzen Zahlen