Leitfaden für Lehrer: Euklidischer Algorithmus

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.

Lektion präsentieren In Classroom teilen Schülerseite anzeigen

Diese Lektion im Unterricht nutzen

Kostenlos, keine Schülerkonten nötig.

Mit Schülern teilen

Die Schüler öffnen die Lektion und üben mit sofortigem Feedback.

Arbeitsblatt zum Drucken

Alle Übungsaufgaben auf Papier, mit separatem Lösungsblatt.

Arbeitsblatt Lösungen

Klassenquiz

10 Fragen zu Faktoren & Vielfache. Die Schüler machen mit einem Namen mit, du siehst alle Ergebnisse.

Für Lehrer

Lernziele

Eine Division mit Rest in der Form $a = q \times b + r$ mit $0 \le r < b$ aufschreiben
Den ggT zweier Zahlen mit dem euklidischen Algorithmus und mit seiner Subtraktionsform bestimmen
Erklären, warum $\text{ggT}(a, b) = \text{ggT}(b, r)$ gilt, und den Algorithmus mit dem Zerlegen eines Rechtecks in Quadrate verbinden
Mit dem ggT Brüche kürzen und $\text{kgV}(a, b) = \frac{a \times b}{\text{ggT}(a, b)}$ berechnen
Entscheiden, ob zwei Zahlen teilerfremd sind, und den Algorithmus mit der Primfaktorzerlegung vergleichen

Voraussetzungen

• Größter gemeinsamer Teiler (ggT): durch Auflisten der Teiler und durch Primfaktorzerlegung
• Kleinstes gemeinsames Vielfaches (kgV) und seine Bedeutung
• Primfaktorzerlegung sowie Primzahlen und zusammengesetzte Zahlen
• Division natürlicher Zahlen mit Rest

Diskussionsstarter

1. Warum muss der Algorithmus immer enden? Was passiert bei jedem Schritt mit den Zahlen?
2. Wenn $d$ die Zahlen $48$ und $18$ teilt, warum muss es dann auch $48 - 2 \times 18 = 12$ teilen?
3. Wann würdest du lieber die Primfaktorzerlegung nutzen und wann den euklidischen Algorithmus?
4. Warum brauchen benachbarte Fibonacci-Zahlen wie $144$ und $89$ so viele Schritte?
5. Wie zeigt das Zerlegen eines Rechtecks in Quadrate dieselben Schritte wie die Divisionen?

Häufige Missverständnisse

Der ggT ist die letzte aufgeschriebene Zahl, oft der Rest $0$ oder ein Quotient

Abhilfe: Kennzeichne in jeder Zeile q und r mit verschiedenen Farben. Kreise den Divisor der Zeile mit Rest $0$ ein und prüfe, dass er beide Ausgangszahlen teilt.

Nach der ersten Division rechnet man mit der ursprünglichen größeren Zahl weiter

Abhilfe: Nutze das Rechteckbild: Sobald die Quadrate abgeschnitten sind, ist die lange Seite weg, und nur das Restrechteck (b mal r) bleibt übrig.

Der Algorithmus ist ein Trick, der zufällig funktioniert

Abhilfe: Zeige mit $48$ , $18$ und $12$ , dass jeder gemeinsame Teiler von $48$ und $18$ auch $12$ teilt und jeder gemeinsame Teiler von $18$ und $12$ auch $48$ teilt. Liste beide Mengen gemeinsamer Teiler auf: Sie sind gleich.

Differenzierungsideen

Für Schüler mit Schwierigkeiten:

• Mit der Subtraktionsform bei kleinen Paaren wie (35, 14) beginnen, bevor dividiert wird
• Rechtecke aus Karopapier verwenden und Quadrate wirklich abschneiden
• Eine Tabelle mit den Spalten a, b, q, r bereitstellen, die Zeile für Zeile ausgefüllt wird

Für Schüler auf Niveau:

• Den Algorithmus auf drei- und vierstellige Paare wie (1071, 462) anwenden
• Brüche wie $\frac{391}{667}$ mit dem ggT kürzen
• kgVs mit $\frac{a \times b}{\text{ggT}(a, b)}$ berechnen und überprüfen

Für fortgeschrittene Schüler:

• Allgemein beweisen, dass $\text{ggT}(a, b) = \text{ggT}(b, r)$ gilt
• Untersuchen, warum benachbarte Fibonacci-Zahlen die meisten Schritte erfordern
• Den erweiterten euklidischen Algorithmus erkunden: $\text{ggT}(a, b)$ als $x \times a + y \times b$ schreiben

Standardausrichtung

6.NS.B.4 (CCSS.MATH.CONTENT.6.NS.B.4)
Den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache zweier natürlicher Zahlen bestimmen
6.NS.B.2 (CCSS.MATH.CONTENT.6.NS.B.2)
Mehrstellige Zahlen sicher mit dem schriftlichen Divisionsverfahren teilen
MP.7 (CCSS.MATH.PRACTICE.MP7)
Strukturen erkennen und nutzen

Lektionsressourcen

visualRechteck in Quadrate
Interaktive Ansicht, die ein Rechteck a mal b in die größten Quadrate zerlegt und dabei jede Zeile a = q × b + r aufschreibt
activityQuadrate auf Karopapier
Die Lernenden zeichnen ein Rechteck 48 mal 18 auf Karopapier und schneiden mit der Schere die größten Quadrate ab, bis nur noch gleiche Quadrate übrig sind
gameggT-Wettrennen
Ein Team nutzt die Primfaktorzerlegung, das andere den euklidischen Algorithmus, bei Paaren wie (1071, 462) und (391, 667)
worksheetÜbung zu den Euklid-Zeilen
Quotienten und Reste eintragen, dann Brüche kürzen und kgVs aus dem ggT berechnen

Lektionsinhalt

Alles, was die Schüler sehen: Definition, Beispiele, typische Fehler, Anwendungen. Zum Öffnen tippen.

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.

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$ .

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

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.

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

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

Mehr zu diesem Thema

Leitfaden für Lehrer: Euklidischer Algorithmus

Diese Lektion im Unterricht nutzen

Für Lehrer

Für Schüler mit Schwierigkeiten:

Für Schüler auf Niveau:

Für fortgeschrittene Schüler:

Lektionsinhalt

Definition

Lösungsbeispiele

Häufige Fehler

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)