Wenn man zwei natürliche Zahlen a und b gegeben hat, dann bestimmt man den größten gemeinsamen Teiler ggT(a,b) von a und b folgendermaßen:
Teile (mit Rest) die größere der beiden Zahlen durch die kleinere.
Teile nun die kleinere der beiden Zahlen durch den Rest, der bei Schritt 1 herauskommt.
Teile nun den Rest der bei Schritt 1 herauskommt durch den Rest der bei Schritt 2 herauskommt.
Teile nun den Rest der bei Schritt 2 herauskommt durch den Rest der bei Schritt 3 herauskommt.
Führe dies so oft durch, bis bei einer Rechnung der Rest 0 herauskommt.
Der Divisor bei dieser Rechnung ist der ggT der Zahlen a und b.
Allgemeine mathematische Schreibweise
Das ganze noch in einer allgemeinen mathematischen Schreibweise:
Man nehme an, dass a größer als b ist:
Rechnung
Beschreibung
q1 und r0 sind dabei Zahlen, die aus der Rechnung (mit Rest) a:b=q1 Rest r0 hervorkommen. r0 ist also der Rest der Division der Zahlen von a und b.
q2 und r1 sind dabei Zahlen, die aus der Rechnung (mit Rest) b:r0=q2 Rest r1 hervorkommen. r1 ist also der Rest der Division der Zahlen b und r0.
q3 und r2 sind dabei Zahlen, die aus der Rechnung (mit Rest) r0:r1=q3 Rest r2 hervorkommen. r2 ist also der Rest der Division der Zahlen r0 und r1.
Führe dies so oft durch, bis bei einer Rechnung Rest 0 herauskommt.
Man kann hier ein Schema erkennen:
Die Zahl rn−1 ist dann der ggT von a und b.
Erklärung am Beispiel
Man hat die zwei Zahlen a=1071 und b=1029.
Rechnung
Beschreibung
1071=q1⋅1029+r0⇒1071=1⋅1029+42
Die Zahlen q1 und r0 errechnet man mit schriftlicher Division mit Rest: 1071:1029421029=1Rest42 damit ist q1=1 und r0=42
1029=q2⋅42+r1⇒1029=24⋅42+21
Die Zahlen q2 und r1 errechnet man so: 1029:841891682142=24Rest21 damit ist q2=24 und r1=21
42=q3⋅21+r2⇒42=2⋅21+0
Die Zahlen q3 und r2 errechnet man so: 42:42021=2Rest0 damit ist q3=2 und r2=0
Also ist r1=21 der größte gemeinsame Teiler von 1071 und 1029:
ggT(1071,1029)=21
Hat dir der Inhalt geholfen?
Übungsaufgaben
Inhalt wird geladen…
Du hast noch nicht genug vom Thema?
Hier findest du noch weitere passende Inhalte zum Thema: