Euklidischer Algorithmus

Name:

Klasse:

Datum:

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)$
2.
Welcher Rest bleibt, wenn du $245$ durch $63$ teilst?
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$
4.
Bestimme $\text{ggT}(56, 21)$ mit dem euklidischen Algorithmus.
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)$ ?
6.
Welches Zahlenpaar ist teilerfremd (ggT $= 1$ )?
1. a) $(12, 18)$
2. b) $(15, 28)$
3. c) $(22, 33)$
4. d) $(14, 21)$
7.
Bestimme $\text{ggT}(252, 105)$ mit dem euklidischen Algorithmus.
8.
Bestimme $\text{ggT}(391, 299)$ mit dem euklidischen Algorithmus.
9.
Kürze $\frac{221}{247}$ vollständig mit dem euklidischen Algorithmus.
10.
Bestimme $\text{kgV}(45, 75)$ mit dem euklidischen Algorithmus und $\text{kgV}(a, b) = \frac{a \times b}{\text{ggT}(a, b)}$ .
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$
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?
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?
14.
Die Fibonacci-Zahlen $144$ und $89$ : Wende den euklidischen Algorithmus an und bestimme ihren ggT.
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$
16.
Bestimme $\text{kgV}(126, 588)$ . Berechne zuerst den ggT mit dem euklidischen Algorithmus.
17.
Bestimme $\text{ggT}(1309, 1001)$ mit dem euklidischen Algorithmus.
18.
Bestimme den ggT von $840$ , $1176$ und $1260$ : zuerst $\text{ggT}(840, 1176)$ , dann den ggT dieses Ergebnisses und $1260$ .