Ist der euklidische Algorithmus schneller als die Primfaktorzerlegung?

Bei kleinen Zahlen wie $12$ und $18$ geht beides schnell. Bei großen Zahlen ist er weit überlegen: Du musst keine einzige Primzahl finden. $\text{ggT}(1071, 462)$ braucht drei Divisionen, während die Zerlegung $1071 = 3^2 \times 7 \times 17$ und $462 = 2 \times 3 \times 7 \times 11$ verlangt.

Was bedeutet es, wenn der Algorithmus mit ggT 1 endet?

Dann sind die beiden Zahlen **teilerfremd**: Sie haben außer $1$ keinen gemeinsamen Teiler. Benachbarte Fibonacci-Zahlen wie $144$ und $89$ sind immer teilerfremd, und bei ihnen braucht der Algorithmus für ihre Größe die meisten Schritte.

Kann ich ihn auch für drei Zahlen verwenden?

Ja, immer zwei auf einmal: $\text{ggT}(a, b, c) = \text{ggT}(\text{ggT}(a, b), c)$. Zum Beispiel ist $\text{ggT}(840, 1176) = 168$ und $\text{ggT}(168, 1260) = 84$, also ist der ggT aller drei Zahlen $84$.

Lehrermaterialien

Euklidischer Algorithmus

Q: Ist es egal, mit welcher Zahl ich anfange?

Ja. Wenn du mit der kleineren Zahl vorne beginnst, lautet die erste Zeile etwa $18 = 0 \times 48 + 18$, und das vertauscht nur die beiden Zahlen. Mit der größeren Zahl zu beginnen spart diesen Schritt.

Finde den größten gemeinsamen Teiler zweier Zahlen durch wiederholte Division mit Rest und nutze ihn zum Kürzen von Brüchen und für das kgV.

Fortgeschritten25 MinLektion

In Classroom teilen

Arbeitsblatt zum Drucken

Definition

Der euklidische Algorithmus ist ein schneller Weg, den größten gemeinsamen Teiler (ggT) zweier natürlicher Zahlen zu finden, ohne Teiler aufzulisten oder Faktorbäume zu zeichnen.

Teile die größere Zahl

a

durch die kleinere Zahl

b

und schreibe das Ergebnis als Division mit Rest:

a = q \times b + r, \quad 0 \le r < b

Dabei ist

q

der Quotient und

r

der Rest. Dann **ersetzt du das Paar

(a, b)

durch

(b, r)

** und teilst erneut. Das wiederholst du, bis der Rest

0

ist. Der letzte Rest ungleich null (der Divisor in der letzten Zeile) ist der ggT.

Beispiel:

\text{ggT}(48, 18)

$48 = 2 \times 18 + 12$
$18 = 1 \times 12 + 6$
$12 = 2 \times 6 + 0$

Der Rest ist

0

, also ist

\text{ggT}(48, 18) = 6

Warum es funktioniert: Wenn eine Zahl

d

sowohl

a

als auch

b

teilt, dann teilt sie auch

r = a - q \times b

. Und wenn

d

sowohl

b

als auch

r

teilt, dann teilt sie auch

a = q \times b + r

. Die Paare

(a, b)

und

(b, r)

haben also genau dieselben gemeinsamen Teiler und damit denselben ggT:

\text{ggT}(a, b) = \text{ggT}(b, r)

Die Zahlen werden bei jedem Schritt kleiner, deshalb endet der Algorithmus immer.

Probier es gleich aus

Beim euklidischen Algorithmus schreibst du

a = q \times b + r

mit

0 \le r < b

. Welches Paar teilst du als Nächstes?

Lösungsbeispiele

Ein Rechteck ist

48

mal

18

groß. Schneide immer wieder die größten möglichen Quadrate ab. Welche Seitenlänge haben die Quadrate, die am Ende genau passen?

Quadrate mit Seite 18 von der langen Seite abschneiden

Zwei Quadrate

18 \times 18

passen,

12

bleibt übrig:

48 = 2 \times 18 + 12

→ Restrechteck

18 \times 12

Quadrate mit Seite 12 vom Rest abschneiden

Ein Quadrat

12 \times 12

passt,

6

bleibt übrig:

18 = 1 \times 12 + 6

→ Restrechteck

12 \times 6

Quadrate mit Seite 6 abschneiden

Zwei Quadrate

6 \times 6

passen genau:

12 = 2 \times 6 + 0

→ Nichts bleibt übrig

Das ganze Rechteck mit dem letzten Quadrat auslegen

6

teilt

48

und

18

\frac{48}{6} \times \frac{18}{6} = 8 \times 3

→

24

Quadrate mit Seite

6

füllen es aus

Antwort: Die Quadrate mit Seite $6$ passen genau, also ist $\text{ggT}(48, 18) = 6$ . Jeder Schnitt entspricht einer Zeile des Algorithmus.

Häufige Fehler

Mit der alten großen Zahl weiterrechnen: nach $48 = 2 \times 18 + 12$ mit $48$ und $12$ weitermachen

Warum es falsch ist: Der Algorithmus funktioniert, weil $\text{ggT}(a, b) = \text{ggT}(b, r)$ gilt. Die Zahl $a$ wird nach der ersten Division nicht mehr gebraucht.

Richtig: Das nächste Paar ist $(18, 12)$ : der alte Divisor und der Rest. Also $18 = 1 \times 12 + 6$ .

$0$ oder den letzten Quotienten als ggT angeben

Warum es falsch ist: Die letzte Zeile hat den Rest $0$ , das sagt dir nur, dass du aufhören kannst. Der Quotient zählt, wie viele Quadrate passen, er ist kein gemeinsamer Teiler.

Richtig: Der ggT ist der letzte Rest ungleich null, also der Divisor in der letzten Zeile. Bei $12 = 2 \times 6 + 0$ ist das $6$ .

Einen zu großen Rest aufschreiben, etwa $1071 = 1 \times 462 + 609$

Warum es falsch ist: Die Gleichung stimmt, aber $609 > 462$ , also passt $462$ noch einmal hinein. Der Rest muss kleiner als der Divisor sein.

Richtig: Nimm den größtmöglichen Quotienten: $1071 = 2 \times 462 + 147$ mit $147 < 462$ .

$a \times b$ als kgV nehmen

Warum es falsch ist: $a \times b$ ist immer ein gemeinsames Vielfaches, aber meist nicht das kleinste: $84 \times 120 = 10080$ zählt den gemeinsamen Teiler $12$ doppelt.

Richtig: Teile durch den ggT: $\text{kgV}(84, 120) = \frac{84 \times 120}{12} = 840$ .

Interaktive Visualisierung

Größte Quadrate im Rechteck: wähle ein Paar

Erste ZahlZweite Zahl

Rechteck 1071 × 462

Drücke auf Nächster Schritt, um die größten passenden Quadrate abzuschneiden.

Du bist dran: Gib in jeder Zeile den Quotienten und den Rest ein

Erste ZahlZweite Zahl

Rechteck 168 × 120

Wie oft passt 120 in 168, und was bleibt übrig?

168 =× 120 +

Interaktiver Sandkasten

Ausdrucksrechner

Probiere diese:

Verlauf

Noch keine Berechnungen

Übungsaufgaben

18 Aufgaben

Aufgabe 1 von 18

Einfach

Beim euklidischen Algorithmus schreibst du

a = q \times b + r

mit

0 \le r < b

. Welches Paar teilst du als Nächstes?

Warum es wichtig ist

Der euklidische Algorithmus ist über 2300 Jahre alt (Euklid hat ihn um 300 v. Chr. aufgeschrieben) und gehört bis heute zu den meistgenutzten Algorithmen der Welt:

Große Zahlen: $1071$ oder $391$ in Primfaktoren zu zerlegen ist mühsam, aber drei oder vier Divisionen liefern sofort den ggT. Bei Zahlen mit Hunderten von Stellen ist die Primfaktorzerlegung praktisch unmöglich, während der euklidische Algorithmus nach höchstens einigen Tausend schnellen Schritten fertig ist.
Brüche: Um $\frac{391}{667}$ zu kürzen, brauchst du $\text{ggT}(391, 667) = 23$ . Durch Zerlegen sieht man das schwer, mit dem Algorithmus geht es schnell.
kgV: Sobald du den ggT kennst, gilt $\text{kgV}(a, b) = \frac{a \times b}{\text{ggT}(a, b)}$ . Ein Algorithmus liefert also beides.
Fliesen, Zahnräder und Bildschirme: die größte quadratische Fliese für einen Boden, wann zwei Zahnräder wieder gleich stehen und warum ein Bildschirm mit $1920 \times 1080$ Pixeln das Format $16:9$ hat, all das läuft auf den ggT hinaus.
Sicherheit im Internet: Verschlüsselungsverfahren wie RSA verwenden eine erweiterte Form dieses Algorithmus jedes Mal, wenn du eine sichere Webseite öffnest.

Anwendungen im echten Leben

Einen Boden mit möglichst großen quadratischen Fliesen auslegen

Ein Fliesenleger möchte einen rechteckigen Boden mit gleich großen quadratischen Fliesen auslegen, ohne eine Fliese zu schneiden. Die größtmögliche Seitenlänge ist der ggT der beiden Längen.

Beispiel:

Eine Platte von $48$ cm mal $18$ cm wird genau mit Quadraten von $6$ cm bedeckt: $\text{ggT}(48, 18) = 6$ , also $8 \times 3 = 24$ Fliesen.

1Probiere es selbst

Ein Flurboden ist $168$ cm mal $120$ cm groß. Er soll mit gleich großen quadratischen Fliesen bedeckt werden, ohne Schneiden und ohne Lücken.

Welche Seitenlänge in cm hat die größte passende quadratische Fliese?

Schritt 1: Schreibe den mathematischen Ausdruck

Bestimme $\text{ggT}(168, 120)$ mit dem euklidischen Algorithmus:

Zahnräder und wiederkehrende Zyklen

Wenn zwei Zahnräder ineinandergreifen, treffen dieselben zwei Zähne erst nach so vielen Zähnen wieder aufeinander, wie das kgV der Zähnezahlen angibt. Der euklidische Algorithmus liefert den ggT, daraus folgt das kgV.

Beispiel:

Zahnräder mit $18$ und $48$ Zähnen: $\text{ggT} = 6$ , also treffen sich dieselben Zähne nach $\frac{18 \times 48}{6} = 144$ Zähnen wieder.

2Probiere es selbst

Ein Fahrradzahnrad hat $84$ Zähne, ein kleines Zahnrad hat $36$ Zähne. Zwei markierte Zähne berühren sich gerade.

Nach wie vielen Zähnen berühren sich die beiden markierten Zähne wieder?

Schritt 1: Schreibe den mathematischen Ausdruck

Bestimme $\text{kgV}(84, 36) = \frac{84 \times 36}{\text{ggT}(84, 36)}$ :

Seitenverhältnisse von Bildschirmen

Aus einer Auflösung wie $1920 \times 1080$ wird ein Seitenverhältnis, indem man beide Zahlen durch ihren ggT teilt.

Beispiel:

$1280 \times 1024$ : $\text{ggT}(1280, 1024) = 256$ , also ist das Verhältnis $5:4$ .

3Probiere es selbst

Ein Monitor hat $1920$ mal $1080$ Pixel. Für sein Seitenverhältnis teilst du beide Zahlen durch ihren ggT.

Wie groß ist $\text{ggT}(1920, 1080)$ ?

Schritt 1: Schreibe den mathematischen Ausdruck

Wende den euklidischen Algorithmus auf $1920$ und $1080$ an:

Wichtige Erkenntnisse

1Euklidischer Algorithmus: Teile $a$ durch $b$ als $a = q \times b + r$ mit $0 \le r < b$ und ersetze dann $(a, b)$ durch $(b, r)$ , bis der Rest $0$ ist
2Der ggT ist der letzte Rest ungleich null, also der Divisor in der letzten Zeile
3Es funktioniert, weil $\text{ggT}(a, b) = \text{ggT}(b, r)$ gilt: Beide Paare haben dieselben gemeinsamen Teiler
4Geometrisch zerlegt der Algorithmus ein Rechteck $a \times b$ in möglichst große Quadrate; die Seite des letzten Quadrats ist der ggT
5Bei der Subtraktionsform (Wechselwegnahme) zieht man immer wieder die kleinere Zahl ab; die Division ist die Abkürzung dafür
6Damit kürzt du Brüche, berechnest $\text{kgV}(a, b) = \frac{a \times b}{\text{ggT}(a, b)}$ und prüfst, ob zwei Zahlen teilerfremd sind (ggT $= 1$ )

Häufig gestellte Fragen

Ja. Wenn du mit der kleineren Zahl vorne beginnst, lautet die erste Zeile etwa

18 = 0 \times 48 + 18

, und das vertauscht nur die beiden Zahlen. Mit der größeren Zahl zu beginnen spart diesen Schritt.

Glossar

Euklidischer Algorithmus: Verfahren für den ggT zweier Zahlen: mit Rest teilen, das Paar durch (Divisor, Rest) ersetzen und wiederholen, bis der Rest $0$ ist
Division mit Rest: Die Darstellung $a = q \times b + r$ mit $0 \le r < b$ , zum Beispiel $1071 = 2 \times 462 + 147$
Quotient: Die Zahl $q$ , die angibt, wie oft $b$ ganz in $a$ passt
Rest: Die Zahl $r$ , die nach der Division übrig bleibt, immer kleiner als der Divisor
Teilerfremd: Zwei Zahlen, deren ggT $1$ ist, etwa $144$ und $89$
Kleinstes gemeinsames Vielfaches (kgV): Die kleinste positive Zahl, die durch beide Zahlen teilbar ist; $\text{kgV}(a, b) = \frac{a \times b}{\text{ggT}(a, b)}$

Formelkarte

Division mit Rest

a = q \times b + r, \quad 0 \le r < b

Eine Zeile des Algorithmus: $q$ ist der Quotient, $r$ der Rest

Kernschritt

\text{ggT}(a, b) = \text{ggT}(b, r)

Ersetze das Paar durch (Divisor, Rest) und wiederhole, bis $r = 0$ ist

kgV aus dem ggT

\text{kgV}(a, b) = \frac{a \times b}{\text{ggT}(a, b)}

Multipliziere die Zahlen und teile durch ihren ggT

Teilerfremde Zahlen

\text{ggT}(a, b) = 1

Die Zahlen haben außer $1$ keinen gemeinsamen Teiler

Heutige ChallengeEine Aufgabe, drei Versuche

Mehr zu diesem Thema

Definition

Lösungsbeispiele

Häufige Fehler

Interaktive Visualisierung

Interaktiver Sandkasten

Ausdrucksrechner

Verlauf

Übungsaufgaben

Warum es wichtig ist

Anwendungen im echten Leben

Einen Boden mit möglichst großen quadratischen Fliesen auslegen

Zahnräder und wiederkehrende Zyklen

Seitenverhältnisse von Bildschirmen

Wichtige Erkenntnisse

Häufig gestellte Fragen

Glossar

Formelkarte

Division mit Rest

Kernschritt

kgV aus dem ggT

Teilerfremde Zahlen

Mehr zu diesem Thema

Teiler und Vielfache

Primfaktorzerlegung

Primzahlen und zusammengesetzte Zahlen

Größter gemeinsamer Teiler (ggT)