Euklidischer Algorithmus

Schreibe bei jeder Aufgabe deinen Lösungsweg auf.

1.
Beim euklidischen Algorithmus schreibst du $a = q \times b + r$ mit $0 \le r < b$ . Welches Paar teilst du als Nächstes?
1. a) $(a, b - r)$
2. b) $(b, r)$
3. c) $(q, r)$
4. d) $(a, r)$
Lösung: $(b, r)$
Das nächste Paar ist $(b, r)$ , weil $\text{ggT}(a, b) = \text{ggT}(b, r)$ gilt. Die Zahl $a$ wird nicht mehr gebraucht.
2.
Welcher Rest bleibt, wenn du $245$ durch $63$ teilst?
Lösung: 56
$245 = 3 \times 63 + 56$ , denn $63 \times 3 = 189$ und $245 - 189 = 56$ . Der Rest $56$ ist kleiner als $63$ , so wie es sein muss.
3.
Der euklidische Algorithmus für $60$ und $42$ liefert $60 = 1 \times 42 + 18$ , $42 = 2 \times 18 + 6$ , $18 = 3 \times 6 + 0$ . Wie groß ist $\text{ggT}(60, 42)$ ?
1. a) $6$
2. b) $0$
3. c) $18$
4. d) $2$
Lösung: $6$
Der Rest wird $0$ in der Zeile $18 = 3 \times 6 + 0$ , also ist der ggT der Divisor dieser Zeile: $6$ . Nicht $0$ (das Stoppzeichen) und nicht $3$ (ein Quotient).
4.
Bestimme $\text{ggT}(56, 21)$ mit dem euklidischen Algorithmus.
Lösung: 7
1. Welcher Rest bleibt, wenn du $56$ durch $21$ teilst? 14
2. Welcher Rest bleibt, wenn du $21$ durch $14$ teilst? 7
3. Welcher Rest bleibt, wenn du $14$ durch $7$ teilst? 0
4. Wie groß ist also $\text{ggT}(56, 21)$ ? 7
5.
Mit der Subtraktionsform für $30$ und $12$ erhältst du $30 - 12 = 18$ , $18 - 12 = 6$ , $12 - 6 = 6$ , $6 - 6 = 0$ . Wie groß ist $\text{ggT}(30, 12)$ ?
Lösung: 6
Das Paar endet als $(6, 6)$ , also ist $\text{ggT}(30, 12) = 6$ . Die zwei Subtraktionen von $12$ sind die Division $30 = 2 \times 12 + 6$ .
6.
Welches Zahlenpaar ist teilerfremd (ggT $= 1$ )?
1. a) $(12, 18)$
2. b) $(15, 28)$
3. c) $(22, 33)$
4. d) $(14, 21)$
Lösung: $(15, 28)$
$28 = 1 \times 15 + 13$ , $15 = 1 \times 13 + 2$ , $13 = 6 \times 2 + 1$ , $2 = 2 \times 1 + 0$ : $\text{ggT}(15, 28) = 1$ . Die anderen haben die gemeinsamen Teiler $7$ , $6$ und $11$ .
7.
Bestimme $\text{ggT}(252, 105)$ mit dem euklidischen Algorithmus.
Lösung: 21
1. Welcher Rest bleibt, wenn du $252$ durch $105$ teilst? 42
2. Welcher Rest bleibt, wenn du $105$ durch $42$ teilst? 21
3. Welcher Rest bleibt, wenn du $42$ durch $21$ teilst? 0
4. Wie groß ist also $\text{ggT}(252, 105)$ ? 21
8.
Bestimme $\text{ggT}(391, 299)$ mit dem euklidischen Algorithmus.
Lösung: 23
$391 = 1 \times 299 + 92$ , $299 = 3 \times 92 + 23$ , $92 = 4 \times 23 + 0$ . Also ist $\text{ggT}(391, 299) = 23$ ( $391 = 17 \times 23$ , $299 = 13 \times 23$ ).
9.
Kürze $\frac{221}{247}$ vollständig mit dem euklidischen Algorithmus.
Lösung: 17/19
1. Welcher Rest bleibt, wenn du $247$ durch $221$ teilst? 26
2. Welcher Rest bleibt, wenn du $221$ durch $26$ teilst? 13
3. $26 = 2 \times 13 + 0$ . Wie groß ist also $\text{ggT}(221, 247)$ ? 13
4. Kürze den Zähler: Wie viel ist $221 \div 13$ ? 17
5. Kürze den Nenner: Wie viel ist $247 \div 13$ ? 19
10.
Bestimme $\text{kgV}(45, 75)$ mit dem euklidischen Algorithmus und $\text{kgV}(a, b) = \frac{a \times b}{\text{ggT}(a, b)}$ .
Lösung: 225
1. Welcher Rest bleibt, wenn du $75$ durch $45$ teilst? 30
2. Welcher Rest bleibt, wenn du $45$ durch $30$ teilst? 15
3. $30 = 2 \times 15 + 0$ . Wie groß ist also $\text{ggT}(45, 75)$ ? 15
4. Wie groß ist $\text{kgV}(45, 75) = \frac{45 \times 75}{15}$ ? 225
11.
Eine Zahl $d$ teilt sowohl $a$ als auch $b$ , und es gilt $a = q \times b + r$ . Welche Zahl muss dann auch durch $d$ teilbar sein?
1. a) $q$
2. b) $r$
3. c) $a + q$
4. d) $q + r$
Lösung: $r$
$r = a - q \times b$ . Wenn $d$ die Zahlen $a$ und $b$ teilt, teilt es auch $a$ minus ein Vielfaches von $b$ , also teilt es $r$ . Deshalb gilt $\text{ggT}(a, b) = \text{ggT}(b, r)$ .
12.
Ein Rechteck ist $77$ mal $28$ groß. Welche Seitenlänge hat das größte Quadrat, mit dem man es genau auslegen kann, ohne Lücken und ohne Schneiden?
Lösung: 7
$77 = 2 \times 28 + 21$ , $28 = 1 \times 21 + 7$ , $21 = 3 \times 7 + 0$ , also $\text{ggT}(77, 28) = 7$ : Quadrate mit Seite $7$ , davon $11 \times 4 = 44$ Stück.
13.
Eine Holzplatte ist $96$ cm mal $60$ cm groß. Sie wird ohne Rest in möglichst große, gleiche Quadrate geschnitten. Wie viele Quadrate erhältst du?
Lösung: 40
1. Welcher Rest bleibt, wenn du $96$ durch $60$ teilst? 36
2. Welcher Rest bleibt, wenn du $60$ durch $36$ teilst? 24
3. Welcher Rest bleibt, wenn du $36$ durch $24$ teilst? 12
4. $24 = 2 \times 12 + 0$ . Welche Seitenlänge in cm hat das größte Quadrat? 12
5. Wie viele solche Quadrate erhältst du aus der Platte? 40
14.
Die Fibonacci-Zahlen $144$ und $89$ : Wende den euklidischen Algorithmus an und bestimme ihren ggT.
Lösung: 1
1. Welcher Rest bleibt, wenn du $144$ durch $89$ teilst? 55
2. Welcher Rest bleibt, wenn du $89$ durch $55$ teilst? 34
3. Welcher Rest bleibt, wenn du $55$ durch $34$ teilst? 21
4. Die Reste gehen weiter mit $13, 8, 5, 3, 2, 1, 0$ . Wie groß ist $\text{ggT}(144, 89)$ ? 1
15.
Was ergibt $\text{ggT}(a, b) \times \text{kgV}(a, b)$ für zwei beliebige natürliche Zahlen $a$ und $b$ ?
1. a) $a \times b$
2. b) $\frac{a}{b}$
3. c) $a + b$
4. d) $a - b$
Lösung: $a \times b$
$\text{ggT}(a, b) \times \text{kgV}(a, b) = a \times b$ . Für $4$ und $6$ : $2 \times 12 = 24 = 4 \times 6$ . Deshalb gilt $\text{kgV}(a, b) = \frac{a \times b}{\text{ggT}(a, b)}$ .
16.
Bestimme $\text{kgV}(126, 588)$ . Berechne zuerst den ggT mit dem euklidischen Algorithmus.
Lösung: 1764
$588 = 4 \times 126 + 84$ , $126 = 1 \times 84 + 42$ , $84 = 2 \times 42 + 0$ , also ist der ggT $42$ und das kgV $\frac{126 \times 588}{42} = 126 \times 14 = 1764$ .
17.
Bestimme $\text{ggT}(1309, 1001)$ mit dem euklidischen Algorithmus.
Lösung: 77
1. Welcher Rest bleibt, wenn du $1309$ durch $1001$ teilst? 308
2. Teile jetzt $1001$ durch $308$ . Wie groß ist der Quotient $q$ ? 3
3. Und der Rest in $1001 = 3 \times 308 + r$ ? 77
4. Welcher Rest bleibt, wenn du $308$ durch $77$ teilst? 0
5. Wie groß ist also $\text{ggT}(1309, 1001)$ ? 77
18.
Bestimme den ggT von $840$ , $1176$ und $1260$ : zuerst $\text{ggT}(840, 1176)$ , dann den ggT dieses Ergebnisses und $1260$ .
Lösung: 84
1. Welcher Rest bleibt, wenn du $1176$ durch $840$ teilst? 336
2. Welcher Rest bleibt, wenn du $840$ durch $336$ teilst? 168
3. $336 = 2 \times 168 + 0$ . Wie groß ist also $\text{ggT}(840, 1176)$ ? 168
4. Welcher Rest bleibt, wenn du $1260$ durch $168$ teilst? 84
5. $168 = 2 \times 84 + 0$ . Wie groß ist also $\text{ggT}(168, 1260)$ ? 84