Algoritme van Euclides

Schrijf bij elke opgave je uitwerking op.

1.
Bij het algoritme van Euclides schrijf je $a = q \times b + r$ met $0 \le r < b$ . Welk paar deel je daarna?
1. a) $(a, b - r)$
2. b) $(b, r)$
3. c) $(q, r)$
4. d) $(a, r)$
Antwoord: $(b, r)$
Het volgende paar is $(b, r)$ , omdat $\text{GGD}(a, b) = \text{GGD}(b, r)$ . Het getal $a$ is niet meer nodig.
2.
Wat is de rest als je $245$ deelt door $63$ ?
Antwoord: 56
$245 = 3 \times 63 + 56$ , want $63 \times 3 = 189$ en $245 - 189 = 56$ . De rest $56$ is kleiner dan $63$ , zoals het hoort.
3.
Het algoritme van Euclides voor $60$ en $42$ geeft $60 = 1 \times 42 + 18$ , $42 = 2 \times 18 + 6$ , $18 = 3 \times 6 + 0$ . Wat is $\text{GGD}(60, 42)$ ?
1. a) $6$
2. b) $0$
3. c) $18$
4. d) $2$
Antwoord: $6$
De rest wordt $0$ in de regel $18 = 3 \times 6 + 0$ , dus de GGD is de deler van die regel: $6$ . Niet $0$ (het stopsignaal) en niet $3$ (een quotiënt).
4.
Bepaal $\text{GGD}(56, 21)$ met het algoritme van Euclides.
Antwoord: 7
1. Wat is de rest als je $56$ deelt door $21$ ? 14
2. Wat is de rest als je $21$ deelt door $14$ ? 7
3. Wat is de rest als je $14$ deelt door $7$ ? 0
4. Wat is dus $\text{GGD}(56, 21)$ ? 7
5.
Met de aftrekmethode op $30$ en $12$ krijg je $30 - 12 = 18$ , $18 - 12 = 6$ , $12 - 6 = 6$ , $6 - 6 = 0$ . Wat is $\text{GGD}(30, 12)$ ?
Antwoord: 6
Het paar eindigt als $(6, 6)$ , dus $\text{GGD}(30, 12) = 6$ . De twee keer $12$ aftrekken is de deling $30 = 2 \times 12 + 6$ .
6.
Welk paar getallen is relatief priem (GGD $= 1$ )?
1. a) $(12, 18)$
2. b) $(15, 28)$
3. c) $(22, 33)$
4. d) $(14, 21)$
Antwoord: $(15, 28)$
$28 = 1 \times 15 + 13$ , $15 = 1 \times 13 + 2$ , $13 = 6 \times 2 + 1$ , $2 = 2 \times 1 + 0$ : $\text{GGD}(15, 28) = 1$ . De andere paren delen $7$ , $6$ en $11$ .
7.
Bepaal $\text{GGD}(252, 105)$ met het algoritme van Euclides.
Antwoord: 21
1. Wat is de rest als je $252$ deelt door $105$ ? 42
2. Wat is de rest als je $105$ deelt door $42$ ? 21
3. Wat is de rest als je $42$ deelt door $21$ ? 0
4. Wat is dus $\text{GGD}(252, 105)$ ? 21
8.
Gebruik het algoritme van Euclides om $\text{GGD}(391, 299)$ te bepalen.
Antwoord: 23
$391 = 1 \times 299 + 92$ , $299 = 3 \times 92 + 23$ , $92 = 4 \times 23 + 0$ . Dus $\text{GGD}(391, 299) = 23$ ( $391 = 17 \times 23$ , $299 = 13 \times 23$ ).
9.
Vereenvoudig $\frac{221}{247}$ zo ver mogelijk met het algoritme van Euclides.
Antwoord: 17/19
1. Wat is de rest als je $247$ deelt door $221$ ? 26
2. Wat is de rest als je $221$ deelt door $26$ ? 13
3. $26 = 2 \times 13 + 0$ . Wat is dus $\text{GGD}(221, 247)$ ? 13
4. Deel de teller: hoeveel is $221 \div 13$ ? 17
5. Deel de noemer: hoeveel is $247 \div 13$ ? 19
10.
Bepaal $\text{kgv}(45, 75)$ met het algoritme van Euclides en $\text{kgv}(a, b) = \frac{a \times b}{\text{GGD}(a, b)}$ .
Antwoord: 225
1. Wat is de rest als je $75$ deelt door $45$ ? 30
2. Wat is de rest als je $45$ deelt door $30$ ? 15
3. $30 = 2 \times 15 + 0$ . Wat is dus $\text{GGD}(45, 75)$ ? 15
4. Wat is $\text{kgv}(45, 75) = \frac{45 \times 75}{15}$ ? 225
11.
Een getal $d$ deelt zowel $a$ als $b$ , en $a = q \times b + r$ . Welk getal moet dan ook deelbaar zijn door $d$ ?
1. a) $q$
2. b) $r$
3. c) $a + q$
4. d) $q + r$
Antwoord: $r$
$r = a - q \times b$ . Als $d$ zowel $a$ als $b$ deelt, deelt het ook $a$ min een veelvoud van $b$ , dus deelt het $r$ . Daarom geldt $\text{GGD}(a, b) = \text{GGD}(b, r)$ .
12.
Een rechthoek is $77$ bij $28$ . Wat is de zijde van het grootste vierkant waarmee je hem precies kunt bedekken, zonder gaten en zonder knippen?
Antwoord: 7
$77 = 2 \times 28 + 21$ , $28 = 1 \times 21 + 7$ , $21 = 3 \times 7 + 0$ , dus $\text{GGD}(77, 28) = 7$ : vierkanten met zijde $7$ , in totaal $11 \times 4 = 44$ .
13.
Een houten plaat is $96$ cm bij $60$ cm. Hij wordt zonder rest in zo groot mogelijke gelijke vierkanten gezaagd. Hoeveel vierkanten krijg je?
Antwoord: 40
1. Wat is de rest als je $96$ deelt door $60$ ? 36
2. Wat is de rest als je $60$ deelt door $36$ ? 24
3. Wat is de rest als je $36$ deelt door $24$ ? 12
4. $24 = 2 \times 12 + 0$ . Wat is de zijde van het grootste vierkant, in cm? 12
5. Hoeveel van zulke vierkanten haal je uit de plaat? 40
14.
De Fibonacci-getallen $144$ en $89$ : pas het algoritme van Euclides toe en bepaal hun GGD.
Antwoord: 1
1. Wat is de rest als je $144$ deelt door $89$ ? 55
2. Wat is de rest als je $89$ deelt door $55$ ? 34
3. Wat is de rest als je $55$ deelt door $34$ ? 21
4. De resten gaan verder met $13, 8, 5, 3, 2, 1, 0$ . Wat is $\text{GGD}(144, 89)$ ? 1
15.
Waaraan is $\text{GGD}(a, b) \times \text{kgv}(a, b)$ gelijk voor twee willekeurige positieve gehele getallen $a$ en $b$ ?
1. a) $a \times b$
2. b) $\frac{a}{b}$
3. c) $a + b$
4. d) $a - b$
Antwoord: $a \times b$
$\text{GGD}(a, b) \times \text{kgv}(a, b) = a \times b$ . Voor $4$ en $6$ : $2 \times 12 = 24 = 4 \times 6$ . Daarom geldt $\text{kgv}(a, b) = \frac{a \times b}{\text{GGD}(a, b)}$ .
16.
Bepaal $\text{kgv}(126, 588)$ . Bereken eerst de GGD met het algoritme van Euclides.
Antwoord: 1764
$588 = 4 \times 126 + 84$ , $126 = 1 \times 84 + 42$ , $84 = 2 \times 42 + 0$ , dus de GGD is $42$ en het kgv is $\frac{126 \times 588}{42} = 126 \times 14 = 1764$ .
17.
Bepaal $\text{GGD}(1309, 1001)$ met het algoritme van Euclides.
Antwoord: 77
1. Wat is de rest als je $1309$ deelt door $1001$ ? 308
2. Deel nu $1001$ door $308$ . Wat is het quotiënt $q$ ? 3
3. En de rest in $1001 = 3 \times 308 + r$ ? 77
4. Wat is de rest als je $308$ deelt door $77$ ? 0
5. Wat is dus $\text{GGD}(1309, 1001)$ ? 77
18.
Bepaal de GGD van $840$ , $1176$ en $1260$ : eerst $\text{GGD}(840, 1176)$ , dan de GGD van die uitkomst en $1260$ .
Antwoord: 84
1. Wat is de rest als je $1176$ deelt door $840$ ? 336
2. Wat is de rest als je $840$ deelt door $336$ ? 168
3. $336 = 2 \times 168 + 0$ . Wat is dus $\text{GGD}(840, 1176)$ ? 168
4. Wat is de rest als je $1260$ deelt door $168$ ? 84
5. $168 = 2 \times 84 + 0$ . Wat is dus $\text{GGD}(168, 1260)$ ? 84