Teilbarkeit · Erklären & üben

Euklidischer Algorithmus

Du berechnest den ggT positiver ganzer Zahlen mit vollständigen Divisionen mit Rest und begründest das Abbruchkriterium.

Zu den Aufgaben

Erklärung 01

Den ggT mit Resten berechnen

Der Euklidische Algorithmus bestimmt den ggT zweier positiver ganzer Zahlen. Statt alle Teiler aufzulisten, ersetzt er das Zahlenpaar wiederholt durch den kleineren Wert und den Divisionsrest. Die gemeinsamen Teiler ändern sich dabei nicht.

Ordne die beiden positiven Zahlen mit der größeren zuerst.
Führe eine Division mit Rest aus.

Jeder Rest ist nichtnegativ und kleiner als der Divisor.

Der obere maßstäbliche Streifen enthält24,24,8; der untere8,8,8. Beide benutzen identische Längeneinheit.

So geht es am Beispiel

Beginne mit 56 und 24.

24 passt zweimal in 56.

Das Produkt ist $\mathsf{2\cdot24=48}$ .

Der Rest ist $\mathsf{56-48=8}$ .

Die vollständige Restgleichung ist $\mathsf{56=2\cdot24+8}$ .

Erklärung 02

Wiederholen bis zum Rest 0

Für die positive größere Zahl a und den positiven Divisor b gilt $\mathsf{a=q\cdot b+r}$ mit $\mathsf{0\leq r<b}$ . Bei r>0 rechne mit b und r weiter. Bei r=0 stoppe: Der Divisor b ist der ggT. Falls vorher schon positive Reste auftraten, ist b der letzte von 0 verschiedene Rest. Geht die allererste Division auf, ist direkt der ursprüngliche kleinere Wert der ggT.

Schreibe jede Division als vollständige Restgleichung.
Übernimm den alten Divisor und den neuen Rest als nächstes Paar.
Stoppe erst beim Rest 0; gib niemals 0 als ggT aus.

$\mathsf{a=q\cdot b+r}$ , $\mathsf{0\leq r<b}$

Vollständige Restfolge; jeder nichtnegative Rest ist kleiner als der jeweilige Divisor.

So geht es am Beispiel

Bestimme den ggT von 56 und 24.

Division mit Rest: $\mathsf{56=2\cdot24+8}$ , wobei $\mathsf{0\leq 8<24}$ .

Setze das Zahlenpaar durch 24 und den Rest 8 fort.

Division mit Rest: $\mathsf{24=3\cdot8+0}$ , wobei $\mathsf{0\leq 0<8}$ .

Der Rest ist 0. Stoppe; der letzte von 0 verschiedene Divisor ist 8.

So geht es am Beispiel

Bestimme den ggT von 91 und 35.

Division mit Rest: $\mathsf{91=2\cdot35+21}$ , wobei $\mathsf{0\leq 21<35}$ .

Setze das Zahlenpaar durch 35 und den Rest 21 fort.

Division mit Rest: $\mathsf{35=1\cdot21+14}$ , wobei $\mathsf{0\leq 14<21}$ .

Setze das Zahlenpaar durch 21 und den Rest 14 fort.

Division mit Rest: $\mathsf{21=1\cdot14+7}$ , wobei $\mathsf{0\leq 7<14}$ .

Setze das Zahlenpaar durch 14 und den Rest 7 fort.

Division mit Rest: $\mathsf{14=2\cdot7+0}$ , wobei $\mathsf{0\leq 0<7}$ .

Der Rest ist 0. Stoppe; der letzte von 0 verschiedene Divisor ist 7.

So geht es am Beispiel

Bestimme den ggT von 45 und 15.

Division mit Rest: $\mathsf{45=3\cdot15+0}$ , wobei $\mathsf{0\leq 0<15}$ .

Der Rest ist 0. Stoppe; der letzte von 0 verschiedene Divisor ist 15.

Erklärung 03

Warum die Reste genügen

Teilt eine positive Zahl d sowohl a als auch b, dann teilt sie auch $\mathsf{r=a-q\cdot b}$ . Umgekehrt teilt jeder gemeinsame Teiler von b und r auch $\mathsf{a=q\cdot b+r}$ . Die gemeinsamen Teiler bleiben also bei jedem Schritt genau gleich. Positive Reste werden streng kleiner. Eine streng fallende Folge positiver ganzer Zahlen kann nicht endlos weitergehen; deshalb erreicht das Verfahren einen Rest 0.

Begründe beide Richtungen der Teilerbeziehung.
Achte auf den echt kleineren Rest.

$\mathsf{\operatorname{\textsf{ggT}}(a,b)=\operatorname{\textsf{ggT}}(b,r)}$

Vollständige Teilerlisten veranschaulichen den unveränderten ggT8 beim Übergang56,24 zu24,8.

So geht es am Beispiel

Zeige die Teilerbeziehung an 56,24 und 8.

8 teilt 56 und 24 und damit auch $\mathsf{56-2\cdot24=8}$ .

Umgekehrt teilt jeder gemeinsame Teiler von 24 und 8 auch $\mathsf{2\cdot24+8=56}$ .

Bei der letzten Division $\mathsf{24=3\cdot8+0}$ ist 8 der größte gemeinsame Teiler.

Erklärung 04

Weiterverweis: Chinesischer Restsatz

Der Chinesische Restsatz behandelt die gemeinsame Lösbarkeit von Restbedingungen. Das ist ein eigenes weiterführendes Thema. Hier wird nur die Verbindung erklärt: Der ggT kann helfen zu prüfen, ob zwei Module teilerfremd sind. Für paarweise teilerfremde positive Module größer als 1 besitzt jedes System von Restvorgaben genau eine Lösung modulo dem Produkt der Module. Ein Lösungsverfahren wird hier nicht entwickelt.

Berechne den ggT zweier Module.
Bei ggT 1 sind sie teilerfremd.

Dieser Abschnitt ist eine Einordnung, kein vollständiger Kurs zum Chinesischen Restsatz.

So geht es am Beispiel

Sind die Module 5 und 8 teilerfremd?

Division mit Rest: $\mathsf{8=1\cdot5+3}$ , wobei $\mathsf{0\leq 3<5}$ .

Setze das Zahlenpaar durch 5 und den Rest 3 fort.

Division mit Rest: $\mathsf{5=1\cdot3+2}$ , wobei $\mathsf{0\leq 2<3}$ .

Setze das Zahlenpaar durch 3 und den Rest 2 fort.

Division mit Rest: $\mathsf{3=1\cdot2+1}$ , wobei $\mathsf{0\leq 1<2}$ .

Setze das Zahlenpaar durch 2 und den Rest 1 fort.

Division mit Rest: $\mathsf{2=2\cdot1+0}$ , wobei $\mathsf{0\leq 0<1}$ .

Der Rest ist 0. Stoppe; der letzte von 0 verschiedene Divisor ist 1.

Jetzt bist du dran

Aufgaben & Lösungen

Rechne zuerst selbst. Nutze den Platz für deinen Rechenweg und vergleiche anschließend mit der Lösung.

01
Aufgabe 1Euklidischer Algorithmus · 1Bestimme den ggT von 36 und 24 mit dem Euklidischen Algorithmus. Notiere alle Restgleichungen.Aufgabe öffnenAufgabe einklappen
Restgleichung 1
Restgleichung 2
ggT
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  Division mit Rest: $\mathsf{36=1\cdot24+12}$ , wobei $\mathsf{0\leq 12<24}$ .
2. Schritt 2 · Erklärung
  Setze das Zahlenpaar durch 24 und den Rest 12 fort.
3. Schritt 3 · Erklärung
  Division mit Rest: $\mathsf{24=2\cdot12+0}$ , wobei $\mathsf{0\leq 0<12}$ .
4. Schritt 4 · Erklärung
  Der Rest ist 0. Stoppe; der letzte von 0 verschiedene Divisor ist 12.
Ergebnisse & Teilantworten
1. Restgleichung 1 $\mathsf{36=1\cdot24+12}$
2. Restgleichung 2 $\mathsf{24=2\cdot12+0}$
3. ggT12.
02
Aufgabe 2Euklidischer Algorithmus · 1Bestimme den ggT von 63 und 42 mit dem Euklidischen Algorithmus. Notiere alle Restgleichungen.Aufgabe öffnenAufgabe einklappen
Restgleichung 1
Restgleichung 2
ggT
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  Division mit Rest: $\mathsf{63=1\cdot42+21}$ , wobei $\mathsf{0\leq 21<42}$ .
2. Schritt 2 · Erklärung
  Setze das Zahlenpaar durch 42 und den Rest 21 fort.
3. Schritt 3 · Erklärung
  Division mit Rest: $\mathsf{42=2\cdot21+0}$ , wobei $\mathsf{0\leq 0<21}$ .
4. Schritt 4 · Erklärung
  Der Rest ist 0. Stoppe; der letzte von 0 verschiedene Divisor ist 21.
Ergebnisse & Teilantworten
1. Restgleichung 1 $\mathsf{63=1\cdot42+21}$
2. Restgleichung 2 $\mathsf{42=2\cdot21+0}$
3. ggT21.
03
Aufgabe 3Euklidischer Algorithmus · 2Bestimme den ggT von 84 und 30 mit dem Euklidischen Algorithmus. Notiere alle Restgleichungen.Aufgabe öffnenAufgabe einklappen
Restgleichung 1
Restgleichung 2
Restgleichung 3
ggT
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  Division mit Rest: $\mathsf{84=2\cdot30+24}$ , wobei $\mathsf{0\leq 24<30}$ .
2. Schritt 2 · Erklärung
  Setze das Zahlenpaar durch 30 und den Rest 24 fort.
3. Schritt 3 · Erklärung
  Division mit Rest: $\mathsf{30=1\cdot24+6}$ , wobei $\mathsf{0\leq 6<24}$ .
4. Schritt 4 · Erklärung
  Setze das Zahlenpaar durch 24 und den Rest 6 fort.
5. Schritt 5 · Erklärung
  Division mit Rest: $\mathsf{24=4\cdot6+0}$ , wobei $\mathsf{0\leq 0<6}$ .
6. Schritt 6 · Erklärung
  Der Rest ist 0. Stoppe; der letzte von 0 verschiedene Divisor ist 6.
Ergebnisse & Teilantworten
1. Restgleichung 1 $\mathsf{84=2\cdot30+24}$
2. Restgleichung 2 $\mathsf{30=1\cdot24+6}$
3. Restgleichung 3 $\mathsf{24=4\cdot6+0}$
4. ggT6.
04
Aufgabe 4Euklidischer Algorithmus · 2Bestimme den ggT von 119 und 34 mit dem Euklidischen Algorithmus. Notiere alle Restgleichungen.Aufgabe öffnenAufgabe einklappen
Restgleichung 1
Restgleichung 2
ggT
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  Division mit Rest: $\mathsf{119=3\cdot34+17}$ , wobei $\mathsf{0\leq 17<34}$ .
2. Schritt 2 · Erklärung
  Setze das Zahlenpaar durch 34 und den Rest 17 fort.
3. Schritt 3 · Erklärung
  Division mit Rest: $\mathsf{34=2\cdot17+0}$ , wobei $\mathsf{0\leq 0<17}$ .
4. Schritt 4 · Erklärung
  Der Rest ist 0. Stoppe; der letzte von 0 verschiedene Divisor ist 17.
Ergebnisse & Teilantworten
1. Restgleichung 1 $\mathsf{119=3\cdot34+17}$
2. Restgleichung 2 $\mathsf{34=2\cdot17+0}$
3. ggT17.
05
Aufgabe 5Euklidischer Algorithmus · 2Bestimme den ggT von 101 und 37 mit dem Euklidischen Algorithmus. Notiere alle Restgleichungen.Aufgabe öffnenAufgabe einklappen
Restgleichung 1
Restgleichung 2
Restgleichung 3
Restgleichung 4
Restgleichung 5
Restgleichung 6
ggT
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  Division mit Rest: $\mathsf{101=2\cdot37+27}$ , wobei $\mathsf{0\leq 27<37}$ .
2. Schritt 2 · Erklärung
  Setze das Zahlenpaar durch 37 und den Rest 27 fort.
3. Schritt 3 · Erklärung
  Division mit Rest: $\mathsf{37=1\cdot27+10}$ , wobei $\mathsf{0\leq 10<27}$ .
4. Schritt 4 · Erklärung
  Setze das Zahlenpaar durch 27 und den Rest 10 fort.
5. Schritt 5 · Erklärung
  Division mit Rest: $\mathsf{27=2\cdot10+7}$ , wobei $\mathsf{0\leq 7<10}$ .
6. Schritt 6 · Erklärung
  Setze das Zahlenpaar durch 10 und den Rest 7 fort.
7. Schritt 7 · Erklärung
  Division mit Rest: $\mathsf{10=1\cdot7+3}$ , wobei $\mathsf{0\leq 3<7}$ .
8. Schritt 8 · Erklärung
  Setze das Zahlenpaar durch 7 und den Rest 3 fort.
9. Schritt 9 · Erklärung
  Division mit Rest: $\mathsf{7=2\cdot3+1}$ , wobei $\mathsf{0\leq 1<3}$ .
10. Schritt 10 · Erklärung
  Setze das Zahlenpaar durch 3 und den Rest 1 fort.
11. Schritt 11 · Erklärung
  Division mit Rest: $\mathsf{3=3\cdot1+0}$ , wobei $\mathsf{0\leq 0<1}$ .
12. Schritt 12 · Erklärung
  Der Rest ist 0. Stoppe; der letzte von 0 verschiedene Divisor ist 1.
Ergebnisse & Teilantworten
1. Restgleichung 1 $\mathsf{101=2\cdot37+27}$
2. Restgleichung 2 $\mathsf{37=1\cdot27+10}$
3. Restgleichung 3 $\mathsf{27=2\cdot10+7}$
4. Restgleichung 4 $\mathsf{10=1\cdot7+3}$
5. Restgleichung 5 $\mathsf{7=2\cdot3+1}$
6. Restgleichung 6 $\mathsf{3=3\cdot1+0}$
7. ggT1.
06
Aufgabe 6Euklidischer Algorithmus · 2Bestimme den ggT von 54 und 18. Erkläre, weshalb schon der erste Schritt endet.Aufgabe öffnenAufgabe einklappen
Restgleichung
ggT
Abbruch
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  Division mit Rest: $\mathsf{54=3\cdot18+0}$ , wobei $\mathsf{0\leq 0<18}$ .
2. Schritt 2 · Erklärung
  Der Rest ist 0. Stoppe; der letzte von 0 verschiedene Divisor ist 18.
3. Schritt 3 · Erklärung
  18 teilt 54 vollständig; es ist kein weiterer positiver Rest nötig.
Ergebnisse & Teilantworten
1. Restgleichung $\mathsf{54=3\cdot18+0}$
2. ggT18.
3. AbbruchDer erste Rest ist 0; der Divisor 18 ist der ggT.
07
Aufgabe 7Euklidischer Algorithmus · 2Prüfe den Schritt $\mathsf{50=2\cdot18+14}$ . Welches Zahlenpaar kommt als Nächstes? Führe das Verfahren zu Ende.Aufgabe öffnenAufgabe einklappen
Nächstes Paar
Restgleichung 1
Restgleichung 2
Restgleichung 3
ggT von 50 und 18
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  Die Gleichung stimmt, denn $\mathsf{2\cdot18+14=50}$ .
2. Schritt 2 · Erklärung
  Der Rest 14 liegt zwischen 0 und 18.
3. Schritt 3 · Erklärung
  Das nächste Paar ist 18 und 14.
4. Schritt 4 · Erklärung
  Division mit Rest: $\mathsf{18=1\cdot14+4}$ , wobei $\mathsf{0\leq 4<14}$ .
5. Schritt 5 · Erklärung
  Setze das Zahlenpaar durch 14 und den Rest 4 fort.
6. Schritt 6 · Erklärung
  Division mit Rest: $\mathsf{14=3\cdot4+2}$ , wobei $\mathsf{0\leq 2<4}$ .
7. Schritt 7 · Erklärung
  Setze das Zahlenpaar durch 4 und den Rest 2 fort.
8. Schritt 8 · Erklärung
  Division mit Rest: $\mathsf{4=2\cdot2+0}$ , wobei $\mathsf{0\leq 0<2}$ .
9. Schritt 9 · Erklärung
  Der Rest ist 0. Stoppe; der letzte von 0 verschiedene Divisor ist 2.
Ergebnisse & Teilantworten
1. Nächstes Paar18 und 14.
2. Restgleichung 1 $\mathsf{18=1\cdot14+4}$
3. Restgleichung 2 $\mathsf{14=3\cdot4+2}$
4. Restgleichung 3 $\mathsf{4=2\cdot2+0}$
5. ggT von 50 und 182.
08
Aufgabe 8Euklidischer Algorithmus · 3Warum ist 0 am Ende des Algorithmus nicht der ggT? Erkläre am Paar 28 und 12.Aufgabe öffnenAufgabe einklappen
Letzter positiver Divisor
Erklärung
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  Division mit Rest: $\mathsf{28=2\cdot12+4}$ , wobei $\mathsf{0\leq 4<12}$ .
2. Schritt 2 · Erklärung
  Setze das Zahlenpaar durch 12 und den Rest 4 fort.
3. Schritt 3 · Erklärung
  Division mit Rest: $\mathsf{12=3\cdot4+0}$ , wobei $\mathsf{0\leq 0<4}$ .
4. Schritt 4 · Erklärung
  Der Rest ist 0. Stoppe; der letzte von 0 verschiedene Divisor ist 4.
5. Schritt 5 · Erklärung
  Die 0 ist der Abbruchrest, nicht der letzte positive Divisor.
Ergebnisse & Teilantworten
1. Letzter positiver Divisor4.
2. ErklärungDer Rest 0 zeigt die vollständige Teilbarkeit durch 4 an. Der ggT ist 4.
09
Aufgabe 9Euklidischer Algorithmus · 3Berechne den ggT von 22 und 35. Sind die beiden Zahlen teilerfremd?Aufgabe öffnenAufgabe einklappen
ggT
Teilerfremd?
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  Division mit Rest: $\mathsf{35=1\cdot22+13}$ , wobei $\mathsf{0\leq 13<22}$ .
2. Schritt 2 · Erklärung
  Setze das Zahlenpaar durch 22 und den Rest 13 fort.
3. Schritt 3 · Erklärung
  Division mit Rest: $\mathsf{22=1\cdot13+9}$ , wobei $\mathsf{0\leq 9<13}$ .
4. Schritt 4 · Erklärung
  Setze das Zahlenpaar durch 13 und den Rest 9 fort.
5. Schritt 5 · Erklärung
  Division mit Rest: $\mathsf{13=1\cdot9+4}$ , wobei $\mathsf{0\leq 4<9}$ .
6. Schritt 6 · Erklärung
  Setze das Zahlenpaar durch 9 und den Rest 4 fort.
7. Schritt 7 · Erklärung
  Division mit Rest: $\mathsf{9=2\cdot4+1}$ , wobei $\mathsf{0\leq 1<4}$ .
8. Schritt 8 · Erklärung
  Setze das Zahlenpaar durch 4 und den Rest 1 fort.
9. Schritt 9 · Erklärung
  Division mit Rest: $\mathsf{4=4\cdot1+0}$ , wobei $\mathsf{0\leq 0<1}$ .
10. Schritt 10 · Erklärung
  Der Rest ist 0. Stoppe; der letzte von 0 verschiedene Divisor ist 1.
11. Schritt 11 · Erklärung
  ggT 1 bedeutet, dass nur der positive Teiler 1 gemeinsam ist.
Ergebnisse & Teilantworten
1. ggT1.
2. Teilerfremd?Ja; der einzige gemeinsame positive Teiler ist 1.

Selbstcheck

Das kann ich jetzt

Ich schreibe jede Division mit ihrem Rest.
Ich übernehme Divisor und Rest als nächstes Paar.
Ich stoppe beim Rest 0 und nenne den letzten positiven Divisor.

AT Academy · Version 2026-10-21