Das geometrische Bild: Quadrate in einem 48 mal 18 Rechteck

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

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

Die Subtraktionsform (Wechselwegnahme)

Bestimme $\text{ggT}(35, 14)$ nur mit Subtraktion: Ziehe immer die kleinere Zahl von der größeren ab.

Ziehe 14 von 35 ab: $35 - 14 = 21$ = Neues Paar $(21, 14)$

Ziehe noch einmal 14 ab: $21 - 14 = 7$ = Neues Paar $(14, 7)$

Jetzt ist 7 kleiner: ziehe 7 ab: $14 - 7 = 7$ = Neues Paar $(7, 7)$

Ziehe noch einmal ab: $7 - 7 = 0$ = Die Zahlen bleiben bei $7$ stehen

Answer: $\text{ggT}(35, 14) = 7$. Zweimal $14$ abziehen ist dasselbe wie eine Division: $35 = 2 \times 14 + 7$. Die Division ist nur eine Abkürzung für viele Subtraktionen.

Ein Klassiker: ggT von 1071 und 462

Bestimme $\text{ggT}(1071, 462)$ mit dem euklidischen Algorithmus.

Teile 1071 durch 462: $462 \times 2 = 924$ und $1071 - 924 = 147$ = $1071 = 2 \times 462 + 147$

Ersetze das Paar durch (462, 147) und teile: $147 \times 3 = 441$ und $462 - 441 = 21$ = $462 = 3 \times 147 + 21$

Ersetze das Paar durch (147, 21) und teile: $21 \times 7 = 147$, es bleibt nichts übrig = $147 = 7 \times 21 + 0$

Lies den letzten Rest ungleich null ab: Der Rest wurde $0$ beim Teilen durch $21$ = $\text{ggT}(1071, 462) = 21$

Answer: $\text{ggT}(1071, 462) = 21$. Probe: $1071 = 21 \times 51$ und $462 = 21 \times 22$.

Einen schwierigen Bruch kürzen

Kürze $\frac{391}{667}$ vollständig.

Teile 667 durch 391: $667 = 1 \times 391 + 276$ = Rest $276$

Teile 391 durch 276: $391 = 1 \times 276 + 115$ = Rest $115$

Teile 276 durch 115: $276 = 2 \times 115 + 46$ = Rest $46$

Teile 115 durch 46, dann 46 durch 23: $115 = 2 \times 46 + 23$ und $46 = 2 \times 23 + 0$ = $\text{ggT}(391, 667) = 23$

Kürze Zähler und Nenner mit 23: $\frac{391 \div 23}{667 \div 23} = \frac{17}{29}$ = $\frac{17}{29}$

Answer: $\frac{391}{667} = \frac{17}{29}$. Da $17$ und $29$ beide Primzahlen sind, lässt sich der Bruch nicht weiter kürzen.

Das kgV aus dem ggT

Bestimme $\text{kgV}(84, 120)$ mit dem euklidischen Algorithmus.

Teile 120 durch 84: $120 = 1 \times 84 + 36$ = Rest $36$

Teile 84 durch 36: $84 = 2 \times 36 + 12$ = Rest $12$

Teile 36 durch 12: $36 = 3 \times 12 + 0$ = $\text{ggT}(84, 120) = 12$

Nutze kgV = a × b ÷ ggT: $\frac{84 \times 120}{12} = \frac{10080}{12}$ = $840$

Probe: $840 \div 84 = 10$ und $840 \div 120 = 7$ = Beide teilen $840$

Answer: $\text{kgV}(84, 120) = 840$.

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

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

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

Mistake: $0$ oder den letzten Quotienten als ggT angeben

Why: 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.

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

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

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

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

Mistake: $a \times b$ als kgV nehmen

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

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

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.

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.

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.

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.

Seitenverhältnisse von Bildschirmen

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

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

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

A: 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.

Q: Ist der euklidische Algorithmus schneller als die Primfaktorzerlegung?

A: 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.

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

A: 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.

Q: Kann ich ihn auch für drei Zahlen verwenden?

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