---
title: "Getaltheorie: delers en priemgetallen"
book: "Wiskunde basisschool en onderbouw"
subject: math
language: nl
chapter: 64
exercises: 10
source: https://one-course.com/books/math/1/nl/chapter/64-getaltheorie-delers-en-priemgetallen
---

# Hoofdstuk 64 — Getaltheorie: delers en priemgetallen

De getaltheorie studeert hele getallen en de manier waarop ze elkaar delen. Haar hoofdrolspelers zijn de priemgetallen, de bouwstenen waaruit elk geheel getal met vermenigvuldigingen wordt samengesteld. Het hoofdstuk eindigt met de [grootste gemene deler](#def-g9-arith-gcd), het juiste gereedschap om [breuken](https://one-course.com/books/math/1/nl/chapter/63-breuken-en-machten#def-g9-fractions-fraction) eens en voor altijd te vereenvoudigen. Dit verhaal gaat, veel verder, door in het bovenbouwvolume en daarna.

## 64.1 Delers en veelvouden

**Definitie 64.1 (Deler, veelvoud).**

Zij $a$ en $b$ positieve gehele getallen. We zeggen dat $b$ het getal $a$ *deelt* (of dat $b$ een deler van $a$ is, of dat $a$ een *veelvoud* van $b$ is) wanneer $a = b \times k$ voor een zeker geheel getal $k$ — dat wil zeggen wanneer de deling van $a$ door $b$ [rest](https://one-course.com/books/math/1/nl/chapter/17-verdelen-en-delen#def-g3-division-remainder) $0$ laat.

**Voorbeeld 64.2.**

De [delers](#def-g9-arith-divisor) van $24$ zijn $1, 2, 3, 4, 6, 8, 12, 24$ — ze komen in paren met [product](https://one-course.com/books/math/1/nl/chapter/10-vermenigvuldigen-eerste-stappen#def-g2-mult-def) $24$: $(1,24)$, $(2,12)$, $(3,8)$, $(4,6)$. De [veelvouden](https://one-course.com/books/math/1/nl/chapter/32-delen-en-veelvouden#def-g5-division-multiple) van $7$ zijn $7, 14, 21, 28, \dots$

**Propositie 64.3 (Deelbaarheidsregels).**

Een geheel getal is [deelbaar](https://one-course.com/books/math/1/nl/chapter/37-gehele-getallen#def-g6-wholes-divisible):

- door $2$ wanneer zijn laatste cijfer [even](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd) is ( $0, 2, 4, 6, 8$ );
- door $5$ wanneer zijn laatste cijfer $0$ of $5$ is;
- door $10$ wanneer zijn laatste cijfer $0$ is;
- door $3$ (respectievelijk $9$ ) wanneer de [som](https://one-course.com/books/math/1/nl/chapter/2-optellen-eerste-stappen#def-g1-addition-def) van zijn cijfers [deelbaar](https://one-course.com/books/math/1/nl/chapter/37-gehele-getallen#def-g6-wholes-divisible) is door $3$ (respectievelijk $9$ );
- door $4$ wanneer zijn laatste twee cijfers een getal vormen dat [deelbaar](https://one-course.com/books/math/1/nl/chapter/37-gehele-getallen#def-g6-wholes-divisible) is door $4$ .

**Bewijs.** *Op dit niveau zonder bewijs aangenomen.* ∎

**Voorbeeld 64.4.**

$7\,215$ eindigt op $5$: [deelbaar](https://one-course.com/books/math/1/nl/chapter/37-gehele-getallen#def-g6-wholes-divisible) door $5$. Zijn cijfersom is $7 + 2 + 1 + 5 = 15$, [deelbaar](https://one-course.com/books/math/1/nl/chapter/37-gehele-getallen#def-g6-wholes-divisible) door $3$ maar niet door $9$: dus is $7\,215$ [deelbaar](https://one-course.com/books/math/1/nl/chapter/37-gehele-getallen#def-g6-wholes-divisible) door $3$, niet door $9$. En inderdaad is $7\,215 = 3 \times 5 \times 481$.

## 64.2 Priemgetallen

**Definitie 64.5 (Priemgetal).**

Een *priemgetal* is een geheel getal $\geq 2$ waarvan de enige [delers](#def-g9-arith-divisor) $1$ en het getal zelf zijn. De priemgetallen onder $30$ zijn

$$
2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29 .
$$

Het getal $1$ is *geen* priemgetal (per afspraak), en een geheel getal $\geq 2$ dat niet priem is, noem je *samengesteld*.

**Stelling 64.6 (Priemfactorontbinding).**

Elk geheel getal $\geq 2$ is een [product](https://one-course.com/books/math/1/nl/chapter/10-vermenigvuldigen-eerste-stappen#def-g2-mult-def) van priemgetallen, en die ontbinding is op de orde van de factoren na uniek.

**Bewijs.** *Op dit niveau zonder bewijs aangenomen.* ∎

**Methode 64.7 (Een geheel getal ontbinden).**

Deel herhaaldelijk door het kleinst mogelijke [priemgetal](#def-g9-arith-prime), tot je bij $1$ uitkomt:

1. probeer $2$ zolang het getal [even](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd) is;
2. probeer daarna $3$ , dan $5$ , dan $7$ , … (alleen priemgetallen);
3. stop wanneer het [quotiënt](https://one-course.com/books/math/1/nl/chapter/17-verdelen-en-delen#def-g3-division-remainder) $1$ is; verzamel de factoren met hun [exponenten](https://one-course.com/books/math/1/nl/chapter/56-machten#def-g8-powers-def) .

Het is genoeg de priemgetallen $p$ te proberen waarvoor $p^2$ het huidige getal niet overtreft: [deelt](#def-g9-arith-divisor) geen van hen het getal, dan is het getal zelf priem.

**Voorbeeld 64.8.**

Ontbind $360$, één deling per keer:

$$
360 = 2 \times 180, \quad
180 = 2 \times 90, \quad
90 = 2 \times 45, \quad
45 = 3 \times 15, \quad
15 = 3 \times 5,
$$

en dus

$$
360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5 = 2^3 \times 3^2
\times 5 .
$$

![De factorboom van 360: elke stap splitst de kleinste priemfactor af (in rood). Lees je de rode bladeren en de laatste 5, dan staat er 360 = 23 × 32 × 5.](https://one-course.com/images/onecourse/chapters/math-1/g9-arith/fig-aae7345aa9ba.svg)

*De factorboom van $360$: elke stap splitst de kleinste priemfactor af (in rood). Lees je de rode bladeren en de laatste $5$, dan staat er $360 = 2^3 \times 3^2 \times 5$.*

**Stelling 64.9 (Euclides).**

Er zijn oneindig veel priemgetallen.

**Bewijs.** Stel dat er maar een eindig aantal zouden zijn, zeg $p_1, p_2, \dots, p_k$, en bekijk

$$
N = p_1 \times p_2 \times \dots \times p_k + 1 .
$$

$N$ door een willekeurige $p_i$ delen laat [rest](https://one-course.com/books/math/1/nl/chapter/17-verdelen-en-delen#def-g3-division-remainder) $1$, dus [deelt](#def-g9-arith-divisor) geen enkele $p_i$ het getal $N$. Maar $N \geq 2$ heeft minstens één priemdeler ([Stelling 64.6](#thm-g9-arith-factorization)) — een [priemgetal](#def-g9-arith-prime) dat niet in onze lijst staat. Tegenspraak: geen enkele eindige lijst kan alle priemgetallen bevatten. ∎

## 64.3 De grootste gemene deler

**Definitie 64.10 (ggd).**

De *grootste gemene deler* van twee positieve gehele getallen $a$ en $b$, geschreven $\gcd(a, b)$, is het grootste getal dat beide [deelt](#def-g9-arith-divisor). Wanneer $\gcd(a, b) = 1$, heten de getallen *relatief priem*: ze hebben geen enkele [deler](#def-g9-arith-divisor) gemeen behalve $1$.

**Voorbeeld 64.11.**

[Delers](#def-g9-arith-divisor) van $18$: $1, 2, 3, 6, 9, 18$. [Delers](#def-g9-arith-divisor) van $24$: $1, 2, 3, 4, 6, 8, 12,
24$. Gemeenschappelijke [delers](#def-g9-arith-divisor): $1, 2, 3, 6$; dus is $\gcd(18, 24) = 6$. De getallen $15$ en $28$ zijn [relatief priem](#def-g9-arith-gcd).

**Propositie 64.12 (ggd uit de ontbindingen).**

De ggd van twee gehele getallen is het [product](https://one-course.com/books/math/1/nl/chapter/10-vermenigvuldigen-eerste-stappen#def-g2-mult-def) van de priemgetallen die in *beide* ontbindingen voorkomen, elk genomen met de *kleinste* van zijn twee [exponenten](https://one-course.com/books/math/1/nl/chapter/56-machten#def-g8-powers-def).

**Bewijs.** *Op dit niveau zonder bewijs aangenomen.* ∎

**Voorbeeld 64.13.**

$360 = 2^3 \times 3^2 \times 5$ en $84 = 2^2 \times 3 \times 7$. Gemeenschappelijke priemgetallen: $2$ ([exponenten](https://one-course.com/books/math/1/nl/chapter/56-machten#def-g8-powers-def) $3$ en $2$: houd $2$) en $3$ ([exponenten](https://one-course.com/books/math/1/nl/chapter/56-machten#def-g8-powers-def) $2$ en $1$: houd $1$). Dus is

$$
\gcd(360, 84) = 2^2 \times 3 = 12 .
$$

**Stelling 64.14 (Algoritme van Euclides).**

Is $a = bq + r$ de deling van $a$ door $b$ met [rest](https://one-course.com/books/math/1/nl/chapter/17-verdelen-en-delen#def-g3-division-remainder) $r$, dan geldt

$$
\gcd(a, b) = \gcd(b, r).
$$

Herhaal je de delingen tot de [rest](https://one-course.com/books/math/1/nl/chapter/17-verdelen-en-delen#def-g3-division-remainder) $0$ is, dan is de ggd van $a$ en $b$ de *laatste [rest](https://one-course.com/books/math/1/nl/chapter/17-verdelen-en-delen#def-g3-division-remainder) verschillend van [nul](https://one-course.com/books/math/1/nl/chapter/1-tellen-tot-20#def-g1-counting-zero)*.

**Bewijs.** Uit $a = bq + r$: elk getal dat $b$ en $r$ [deelt](#def-g9-arith-divisor), [deelt](#def-g9-arith-divisor) ook $bq + r = a$; en uit $r = a - bq$: elk getal dat $a$ en $b$ [deelt](#def-g9-arith-divisor), [deelt](#def-g9-arith-divisor) ook $r$. De paren $(a, b)$ en $(b, r)$ hebben dus precies dezelfde gemeenschappelijke [delers](#def-g9-arith-divisor) — en in het bijzonder dezelfde grootste. Omdat de [resten](https://one-course.com/books/math/1/nl/chapter/17-verdelen-en-delen#def-g3-division-remainder) strikt dalen, stopt het algoritme, en $\gcd(x, 0) = x$ levert de laatste [rest](https://one-course.com/books/math/1/nl/chapter/17-verdelen-en-delen#def-g3-division-remainder) verschillend van [nul](https://one-course.com/books/math/1/nl/chapter/1-tellen-tot-20#def-g1-counting-zero). ∎

**Voorbeeld 64.15.**

Bereken $\gcd(1071, 462)$:

$$
\begin{align*}
1071 &= 462 \times 2 + 147, \\
462 &= 147 \times 3 + 21, \\
147 &= 21 \times 7 + 0 .
\end{align*}
$$

De laatste [rest](https://one-course.com/books/math/1/nl/chapter/17-verdelen-en-delen#def-g3-division-remainder) verschillend van [nul](https://one-course.com/books/math/1/nl/chapter/1-tellen-tot-20#def-g1-counting-zero) is $21$: $\gcd(1071, 462) = 21$.

**Methode 64.16 (Een breuk volledig vereenvoudigen).**

Om $\dfrac ab$ in eenvoudigste vorm te schrijven:

1. bereken $d = \gcd(a, b)$ , bijvoorbeeld met het algoritme van Euclides;
2. deel [teller](https://one-course.com/books/math/1/nl/chapter/24-eerste-breuken#def-g4-fractions-def) en [noemer](https://one-course.com/books/math/1/nl/chapter/24-eerste-breuken#def-g4-fractions-def) door $d$ : $\dfrac ab = \dfrac{a \div d}{b \div d}$ ;
3. de [breuk](https://one-course.com/books/math/1/nl/chapter/63-breuken-en-machten#def-g9-fractions-fraction) die je zo krijgt is *onvereenvoudigbaar* : haar [teller](https://one-course.com/books/math/1/nl/chapter/24-eerste-breuken#def-g4-fractions-def) en [noemer](https://one-course.com/books/math/1/nl/chapter/24-eerste-breuken#def-g4-fractions-def) zijn [relatief priem](#def-g9-arith-gcd) .

**Voorbeeld 64.17.**

$\dfrac{462}{1071} = \dfrac{462 \div 21}{1071 \div 21} = \dfrac{22}{51}$, en $\gcd(22, 51) = 1$: onvereenvoudigbaar.

## 64.4 Oefeningen

**Oefening 64.1 ★.**

Noem alle [delers](#def-g9-arith-divisor) van $36$, van $45$ en van $17$.

**Oplossing van Oefening 64.1.**

[Delers](#def-g9-arith-divisor) van $36$: $1, 2, 3, 4, 6, 9, 12, 18, 36$. [Delers](#def-g9-arith-divisor) van $45$: $1, 3, 5, 9, 15, 45$. [Delers](#def-g9-arith-divisor) van $17$: alleen $1$ en $17$ ($17$ is priem).

**Oefening 64.2 ★.**

Bepaal met de deelbaarheidsregels of $2\,346$ [deelbaar](https://one-course.com/books/math/1/nl/chapter/37-gehele-getallen#def-g6-wholes-divisible) is door $2$, door $3$, door $4$, door $5$ en door $9$.

**Oplossing van Oefening 64.2.**

$2\,346$ eindigt op $6$: [deelbaar](https://one-course.com/books/math/1/nl/chapter/37-gehele-getallen#def-g6-wholes-divisible) door $2$, niet door $5$. Cijfersom $2 + 3 + 4 + 6 = 15$: [deelbaar](https://one-course.com/books/math/1/nl/chapter/37-gehele-getallen#def-g6-wholes-divisible) door $3$, niet door $9$. Laatste twee cijfers $46$, en $46 = 4 \times 11 + 2$ is niet [deelbaar](https://one-course.com/books/math/1/nl/chapter/37-gehele-getallen#def-g6-wholes-divisible) door $4$: $2\,346$ is niet [deelbaar](https://one-course.com/books/math/1/nl/chapter/37-gehele-getallen#def-g6-wholes-divisible) door $4$.

**Oefening 64.3 ★.**

Geef de priemfactorontbinding van $72$, $150$, $210$ en $121$.

**Oplossing van Oefening 64.3.**

$72 = 2^3 \times 3^2$; $150 = 2 \times 3 \times 5^2$; $210 = 2 \times 3 \times 5 \times 7$; $121 = 11^2$.

**Oefening 64.4 ★.**

Is $101$ priem? En $91$? En $143$? Verantwoord met de stopregel van [Methode 64.7](#met-g9-arith-factorization).

**Oplossing van Oefening 64.4.**

$101$: toets de priemgetallen $p$ met $p^2 \leq 101$, dat wil zeggen $2, 3, 5, 7$. Geen van hen [deelt](#def-g9-arith-divisor) $101$ ([oneven](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd), cijfersom $2$, eindigt niet op $0$ of $5$, en $101 = 7 \times 14 + 3$): $101$ is priem.

$91 = 7 \times 13$: niet priem.

$143 = 11 \times 13$: niet priem.

**Oefening 64.5 ★.**

Bereken $\gcd(48, 60)$ op twee manieren: door de gemeenschappelijke [delers](#def-g9-arith-divisor) op te noemen, en uit de priemfactorontbindingen.

**Oplossing van Oefening 64.5.**

Gemeenschappelijke [delers](#def-g9-arith-divisor) van $48$ en $60$: de [delers](#def-g9-arith-divisor) van $48$ zijn $1, 2, 3, 4, 6, 8, 12, 16, 24, 48$; de [delers](#def-g9-arith-divisor) van $60$ zijn $1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$; de gemeenschappelijke zijn $1, 2, 3, 4, 6, 12$, dus is $\gcd(48,60) = 12$.

Met de ontbinding: $48 = 2^4 \times 3$ en $60 = 2^2 \times 3 \times 5$; gemeenschappelijke priemgetallen met de kleinste [exponenten](https://one-course.com/books/math/1/nl/chapter/56-machten#def-g8-powers-def): $2^2 \times 3 = 12$.

**Oefening 64.6 ★★.**

Bereken met het algoritme van Euclides $\gcd(255, 154)$, en daarna $\gcd(1053, 325)$. Schrijf elke deling uit.

**Oplossing van Oefening 64.6.**

$\gcd(255, 154)$:

$$
\begin{align*}
255 &= 154 \times 1 + 101, \\
154 &= 101 \times 1 + 53, \\
101 &= 53 \times 1 + 48, \\
53 &= 48 \times 1 + 5, \\
48 &= 5 \times 9 + 3, \\
5 &= 3 \times 1 + 2, \\
3 &= 2 \times 1 + 1, \\
2 &= 1 \times 2 + 0 .
\end{align*}
$$

Laatste [rest](https://one-course.com/books/math/1/nl/chapter/17-verdelen-en-delen#def-g3-division-remainder) verschillend van [nul](https://one-course.com/books/math/1/nl/chapter/1-tellen-tot-20#def-g1-counting-zero): $\gcd(255, 154) = 1$ (ze zijn [relatief priem](#def-g9-arith-gcd)).

$\gcd(1053, 325)$:

$$
\begin{align*}
1053 &= 325 \times 3 + 78, \\
325 &= 78 \times 4 + 13, \\
78 &= 13 \times 6 + 0 .
\end{align*}
$$

$\gcd(1053, 325) = 13$.

**Oefening 64.7 ★★.**

Maak de [breuk](https://one-course.com/books/math/1/nl/chapter/63-breuken-en-machten#def-g9-fractions-fraction) $\dfrac{588}{504}$ onvereenvoudigbaar. (Bereken de ggd met de methode van je keuze, en deel dan.)

**Oplossing van Oefening 64.7.**

Algoritme van Euclides: $588 = 504 \times 1 + 84$; $504 = 84 \times 6 + 0$: $\gcd(588, 504) = 84$. Dan is

$$
\frac{588}{504} = \frac{588 \div 84}{504 \div 84} = \frac{7}{6},
$$

en dat is onvereenvoudigbaar.

**Oefening 64.8 ★★.**

Een bloemist heeft $84$ rozen en $126$ tulpen en wil er identieke boeketten van maken, met alle bloemen op en zo veel boeketten mogelijk. Hoeveel boeketten kan ze maken, en wat zit er in elk?

**Oplossing van Oefening 64.8.**

Het aantal boeketten moet zowel $84$ als $126$ delen; het grootst mogelijke is $\gcd(84, 126)$. Ontbindingen: $84 = 2^2 \times 3 \times 7$, $126 = 2 \times 3^2 \times 7$, dus is de ggd $2 \times 3 \times 7 = 42$. Ze kan $42$ boeketten maken, met in elk $\frac{84}{42} = 2$ rozen en $\frac{126}{42} = 3$ tulpen.

**Oefening 64.9 ★★.**

Twee veerboten vertrekken om 8:00 van dezelfde kade. De ene vaart elke $24$ minuten uit, de andere elke $36$ minuten. Hoe laat vertrekken ze de volgende keer samen? (Zoek het kleinste gemeenschappelijke [veelvoud](#def-g9-arith-divisor) van $24$ en $36$; de ontbindingen helpen.)

**Oplossing van Oefening 64.9.**

We hebben het kleinste gemeenschappelijke [veelvoud](#def-g9-arith-divisor) nodig. $24 = 2^3 \times 3$ en $36 = 2^2 \times 3^2$; neem je elk [priemgetal](#def-g9-arith-prime) met de *grootste* [exponent](https://one-course.com/books/math/1/nl/chapter/56-machten#def-g8-powers-def), dan is $\lcm = 2^3 \times 3^2 = 72$. De veerboten vertrekken de volgende keer samen $72$ minuten na 8:00, om 9:12.

**Oefening 64.10 ★★★.**

Zij $n$ een positief geheel getal.

1. Toon aan dat $\gcd(n, n+1) = 1$ (opeenvolgende gehele getallen zijn altijd [relatief priem](#def-g9-arith-gcd) ).
2. Leid af dat de [breuk](https://one-course.com/books/math/1/nl/chapter/63-breuken-en-machten#def-g9-fractions-fraction) $\dfrac{n}{n+1}$ altijd onvereenvoudigbaar is.

**Oplossing van Oefening 64.10.**

*1.* Elke gemeenschappelijke [deler](#def-g9-arith-divisor) $d$ van $n$ en $n+1$ [deelt](#def-g9-arith-divisor) ook hun [verschil](https://one-course.com/books/math/1/nl/chapter/3-aftrekken-eerste-stappen#ex-g1-subtraction-difference) $(n+1) - n = 1$, dus is $d = 1$: $\gcd(n, n+1) = 1$.

*2.* Een [breuk](https://one-course.com/books/math/1/nl/chapter/63-breuken-en-machten#def-g9-fractions-fraction) is onvereenvoudigbaar precies wanneer haar [teller](https://one-course.com/books/math/1/nl/chapter/24-eerste-breuken#def-g4-fractions-def) en [noemer](https://one-course.com/books/math/1/nl/chapter/24-eerste-breuken#def-g4-fractions-def) [relatief priem](#def-g9-arith-gcd) zijn, en dat is volgens deel 1 het geval voor $n$ en $n + 1$.

## 64.5 Opgave: waterkannen, cicaden en honderd kluisjes

**Probleem 64.1.**

Weekendopgave — de ggd beslist welke hoeveelheden twee kannen kunnen afmeten; priemgetallen beschermen cicaden; en de kluisjes die open blijven zijn de volkomen kwadraten

Drie puzzels die op raadsels lijken en in werkelijkheid getaltheorie zijn: water afmeten met kannen zonder maatstreep (de ggd in vermomming), levenscycli van insecten die tot priemgetallen zijn geëvolueerd, en een beroemde gang met honderd kluisjes waarvan de eindstand door het tellen van [delers](#def-g9-arith-divisor) wordt beslist. Alles draait op de machinerie van dit hoofdstuk: deelbaarheid, priemfactorontbinding ([Stelling 64.6](#thm-g9-arith-factorization)) en het algoritme van Euclides ([Stelling 64.14](#thm-g9-arith-euclidalgo)).

**Deel I — De waterkannen.** Je staat bij een fontein met twee kannen zonder maatstreep, van $5$ L en $3$ L. Toegestane zetten: een kan tot de rand vullen, een kan volledig leegmaken, de ene kan in de andere gieten tot de bron leeg of het doel vol is.

1. Meet precies $1$ L af. (Beschrijf je reeks zetten en de [inhoud](https://one-course.com/books/math/1/nl/chapter/12-geld-en-maten#def-g2-measure-units) van de twee kannen na elke zet.)
2. Meet precies $4$ L af — de puzzel uit een beroemde actiefilm. (Het kan in zes zetten.)
3. Welke hele aantallen liter van $1$ tot $8$ kun je voorleggen (in één kan, of verdeeld over de twee)? Vul de lijst aan en hergebruik je reeksen.
4. Nieuwe kannen: $6$ L en $4$ L. Probeer $1$ L af te meten — en leg daarna uit waarom het hopeloos is: ga na dat elk van de drie toegestane zetten de [inhoud](https://one-course.com/books/math/1/nl/chapter/12-geld-en-maten#def-g2-measure-units) van elke kan een [veelvoud](#def-g9-arith-divisor) van $2$ laat, zodat elke bereikbare hoeveelheid [even](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd) is.
5. Het argument van vraag 4 werkt in het algemeen: met kannen van $a$ en $b$ liter is elke bereikbare hoeveelheid een [veelvoud](#def-g9-arith-divisor) van $\gcd(a, b)$ . Bereken $\gcd(6, 4)$ en $\gcd(5, 3)$ , en zeg wat de wet voor elk paar kannen voorspelt.

**Deel II — Euclides bij de fontein.**

6. Bereken met het algoritme van Euclides: $\gcd(91, 65)$ en $\gcd(2\,026, 46)$ .
7. Leg in je eigen woorden uit waarom de hoeveelheden die in de kannen opduiken, de [resten](https://one-course.com/books/math/1/nl/chapter/17-verdelen-en-delen#def-g3-division-remainder) van Euclides in vermomming zijn: vul met kannen van $13$ L en $5$ L herhaaldelijk de kleine kan en giet die in de grote leeg (en maak de grote kan leeg zodra hij vol is). Welke nieuwe hoeveelheden duiken het eerst op — en vergelijk ze met de [resten](https://one-course.com/books/math/1/nl/chapter/17-verdelen-en-delen#def-g3-division-remainder) in het algoritme van Euclides voor $(13, 5)$ .
8. Leid het antwoord van de kampioen af: kun je met kannen van $13$ en $5$ liter precies $1$ L afmeten? Verantwoord het in één regel met vraag 5 en $\gcd(13, 5)$ .
9. Een snel bewijs van relatieve priemheid in de stijl van [Oefening 64.10](#exo-g9-arith-10) : toon aan dat $\gcd(n, 2n + 1) = 1$ voor elk positief geheel getal $n$ . (Wat moet een gemeenschappelijke [deler](#def-g9-arith-divisor) van $n$ en $2n + 1$ delen?)
10. Twee bussen vertrekken om 7:00 samen van de eindhalte; de ene rijdt elke $12$ minuten uit, de andere elke $18$ . Noem de volgende vertrektijden van elk en zoek het eerste ogenblik waarop ze weer samen vertrekken. Ga op dit voorbeeld de mooie wet na: (eerste gemeenschappelijke [veelvoud](#def-g9-arith-divisor) ) $\times$ ggd $=$ [product](https://one-course.com/books/math/1/nl/chapter/10-vermenigvuldigen-eerste-stappen#def-g2-mult-def) van de twee getallen — en toets ze nog eens op $5$ en $3$ .

**Deel III — Cicaden, [delers](#def-g9-arith-divisor) en kluisjes.**

11. Bepaalde Noord-Amerikaanse cicaden komen slechts elke $17$ jaar boven; stel dat de populatie van een roofdier elke $4$ jaar een piek kent. Gebeuren beide dit jaar, over hoeveel jaar valt een opkomst dan voor het eerst weer samen met een piek? Dezelfde vraag als de cyclus van de cicaden $16$ jaar zou zijn — hoe vaak zouden ze dan afgeslacht worden? Leg in één zin uit waarom de evolutie de cyclus naar een *priem* lengte duwde.
12. Tel met de ontbinding $360 = 2^3 \times 3^2 \times 5$ de [delers](#def-g9-arith-divisor) van $360$ zonder ze op te noemen: een [deler](#def-g9-arith-divisor) kiest een [exponent](https://one-course.com/books/math/1/nl/chapter/56-machten#def-g8-powers-def) voor $2$ (vier keuzen: $0, 1, 2, 3$ ), een voor $3$ en een voor $5$ . Hoeveel [delers](#def-g9-arith-divisor) zijn er in totaal?
13. Toon aan dat in de ontbinding van een volkomen kwadraat $n = m^2$ elk [priemgetal](#def-g9-arith-prime) een *[even](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd)* [exponent](https://one-course.com/books/math/1/nl/chapter/56-machten#def-g8-powers-def) draagt. Leid af, zonder één vierkantswortel te berekenen, dat $360$ geen volkomen kwadraat is.
14. Koppel elke [deler](#def-g9-arith-divisor) $d$ van $n$ aan zijn partner $\frac{n}{d}$ (voor $n = 36$ : $1 \leftrightarrow 36$ , $2 \leftrightarrow 18$ , $3 \leftrightarrow 12$ , $4 \leftrightarrow 9$ , $6 \leftrightarrow 6$ ). Wanneer is een [deler](#def-g9-arith-divisor) zijn eigen partner? Leid het criterium af: $n$ heeft een *[oneven](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd)* aantal [delers](#def-g9-arith-divisor) precies dan als $n$ een volkomen kwadraat is. Ga het na op $36$ en op $360$ .
15. De honderd kluisjes. De kluisjes $1$ tot $100$ zijn in het begin dicht. Leerling $1$ verandert de stand van elk kluisje; leerling $2$ verandert de stand van de kluisjes $2, 4, 6, \dots$ ; leerling $k$ verandert de stand van de [veelvouden](https://one-course.com/books/math/1/nl/chapter/32-delen-en-veelvouden#def-g5-division-multiple) van $k$ ; en zo verder tot leerling $100$ . Leg uit welke leerlingen kluisje $n$ aanraken, hoeveel keer de stand ervan verandert, en — met vraag 14 — precies welke kluisjes op het einde open staan. Hoeveel staan er open?

**Oplossing van Probleem 64.1.**

**1.** Vul de kan van $3$ en giet die in de kan van $5$ ([inhoud](https://one-course.com/books/math/1/nl/chapter/12-geld-en-maten#def-g2-measure-units) $0/3 \to 3$ in de grote). Vul de kan van $3$ opnieuw en giet in de kan van $5$ tot die vol is: de grote kan neemt er nog maar $2$ op, zodat er

$$
3 - 2 = 1 \text{ L in de kleine kan blijft.}
$$

Zetten: vul $3$; giet $3 \to 5$; vul $3$; giet $3 \to 5$.

**2.** Vul de kan van $5$; giet in die van $3$ (er blijft $2$ in de grote); maak die van $3$ leeg; giet de $2$ in die van $3$; vul die van $5$; giet in die van $3$ tot ze vol is — er gaat $1$ in, zodat er $\mathbf{4}$ L in de grote kan blijft. Zes zetten.

**3.** Alle: $1$ (vraag 1), $2$ (na twee zetten van vraag 2), $3$ en $5$ (één vulling), $4$ (vraag 2), $6 = 3 + 3$ (een volle kleine kan plus $3$ in de grote gegoten), $7 = 5 + 2$, $8 = 5 + 3$ (beide vol). Elke hele hoeveelheid van $1$ tot $8$ L is met de kan van $5$ en die van $3$ af te meten.

**4.** Bij het begin bevatten beide kannen $0$, een [veelvoud](#def-g9-arith-divisor) van $2$. Vullen zet een [inhoud](https://one-course.com/books/math/1/nl/chapter/12-geld-en-maten#def-g2-measure-units) op $6$ of $4$: [even](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd). Leegmaken zet ze op $0$: [even](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd). Gieten verplaatst wat water tussen kannen waarvan de [inhoud](https://one-course.com/books/math/1/nl/chapter/12-geld-en-maten#def-g2-measure-units) [even](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd) was, en de gegoten hoeveelheid is een [verschil](https://one-course.com/books/math/1/nl/chapter/3-aftrekken-eerste-stappen#ex-g1-subtraction-difference) van [even](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd) getallen (de overblijvende ruimte, of de beschikbare hoeveelheid): alle [inhouden](https://one-course.com/books/math/1/nl/chapter/12-geld-en-maten#def-g2-measure-units) blijven dus eeuwig [even](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd). Een [oneven](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd) doel zoals $1$ L is onbereikbaar.

**5.** $\gcd(6, 4) = 2$: alleen [even](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd) hoeveelheden — bevestigd door vraag 4. $\gcd(5, 3) = 1$: de wet laat elke hele hoeveelheid toe, en vraag 3 heeft ze alle verwezenlijkt. De ggd is precies de maateenheid van de kannen.

**6.** $91 = 1 \times 65 + 26$; $65 = 2 \times 26 + 13$; $26 = 2 \times 13 + 0$: $\gcd(91, 65) = 13$. En $2\,026 = 44 \times 46 + 2$; $46 = 23 \times 2 + 0$: $\gcd(2\,026, 46) = 2$.

**7.** Herhaaldelijk $5$ in de kan van $13$ gieten: na twee vullingen bevat de grote kan $10$; van de derde vulling gaat er maar $3$ in, zodat er $5 - 3 = 2$ in de kleine kan blijft — de [rest](https://one-course.com/books/math/1/nl/chapter/17-verdelen-en-delen#def-g3-division-remainder) van $13$ bij deling door $5$ was $3$, en de hoeveelheden $3$ (de ruimte) en $2$ (wat overblijft) zijn precies de getallen van Euclides ($13 = 2 \times 5 + 3$, $5 = 1 \times 3 + 2$). Ga je door, dan duikt $3 - 2 = 1$ op: de volgende [rest](https://one-course.com/books/math/1/nl/chapter/17-verdelen-en-delen#def-g3-division-remainder) van het algoritme. De fontein voert de delingen van Euclides met water uit.

**8.** $\gcd(13, 5) = 1$, dus laat de wet van vraag 5 elke hele hoeveelheid toe — en de cascade van vraag 7 bracht $1$ L werkelijk voort. Ja.

**9.** Een gemeenschappelijke [deler](#def-g9-arith-divisor) van $n$ en $2n + 1$ [deelt](#def-g9-arith-divisor) $2n + 1 - 2 \times n = 1$: hij moet $1$ zijn. Bijgevolg is $\gcd(n, 2n+1) = 1$, altijd.

**10.** Bus A: 7:12, 7:24, 7:36, 7:48, 8:00 …; bus B: 7:18, 7:36, 7:54 … Eerste gemeenschappelijke vertrek: 7:36, na $36$ minuten — het eerste gemeenschappelijke [veelvoud](#def-g9-arith-divisor) van $12$ en $18$. De wet: $36 \times \gcd(12, 18) = 36 \times 6 = 216 = 12 \times 18$. Voor $5$ en $3$: eerste gemeenschappelijke [veelvoud](#def-g9-arith-divisor) $15$, en $15 \times \gcd(5,3) = 15 \times 1 = 15 = 5 \times 3$.

**11.** Met een cyclus van $17$ jaar: de volgende samenloop is het eerste gemeenschappelijke [veelvoud](#def-g9-arith-divisor) van $17$ en $4$; omdat $\gcd(17, 4) = 1$, is dat $17 \times 4 = 68$ jaar — de cicaden ontmoeten de piek één keer op vier opkomsten. Met een cyclus van $16$ jaar: $16$ is een [veelvoud](#def-g9-arith-divisor) van $4$, dus treft *elke* opkomst een piek. Een priemlengte van de cyclus heeft met geen enkele kortere cyclus van een roofdier een factor gemeen, en drijft de samenlopen zo ver mogelijk uit elkaar: getaltheorie als camouflage.

**12.** Vier keuzen van [exponent](https://one-course.com/books/math/1/nl/chapter/56-machten#def-g8-powers-def) voor $2$, drie voor $3$, twee voor $5$: $4 \times 3 \times 2 = 24$ [delers](#def-g9-arith-divisor).

**13.** Is $m = 2^{a} \times 3^{b} \times \cdots$, dan is $m^2 = 2^{2a} \times 3^{2b} \times \cdots$: elke [exponent](https://one-course.com/books/math/1/nl/chapter/56-machten#def-g8-powers-def) is verdubbeld, en dus [even](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd). In $360 = 2^3 \times 3^2 \times 5$ zijn de [exponenten](https://one-course.com/books/math/1/nl/chapter/56-machten#def-g8-powers-def) van $2$ en van $5$ [oneven](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd): $360$ is geen volkomen kwadraat.

**14.** Een [deler](#def-g9-arith-divisor) is zijn eigen partner precies wanneer $d = \frac nd$, dat wil zeggen $n = d^2$: alleen kwadraten hebben zo’n middelste [deler](#def-g9-arith-divisor). Voor alle andere $n$ vallen de [delers](#def-g9-arith-divisor) in paren uiteen, een [even](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd) aantal. Dus: [oneven](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd) aantal [delers](#def-g9-arith-divisor) $\Leftrightarrow$ volkomen kwadraat. Controle: $36$ heeft de [delers](#def-g9-arith-divisor) $1, 2, 3, 4, 6, 9, 12, 18, 36$ — negen ervan, [oneven](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd), en $36 = 6^2$; terwijl $360$ er $24$ heeft (vraag 12), [even](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd), en geen kwadraat is (vraag 13).

**15.** De stand van kluisje $n$ wordt één keer veranderd door elke leerling $k$ wiens nummer $n$ [deelt](#def-g9-arith-divisor): in totaal dus even veel keer als $n$ [delers](#def-g9-arith-divisor) heeft. Een kluisje eindigt *open* wanneer zijn stand een [oneven](https://one-course.com/books/math/1/nl/chapter/14-getallen-tot-10-000#def-g3-numbers-evenodd) aantal keer is veranderd — volgens vraag 14 precies wanneer $n$ een volkomen kwadraat is. De open kluisjes: $1, 4, 9, 16, 25, 36, 49, 64, 81, 100$ — tien ervan.