Wiskunde basisschool en onderbouw · Grades 1–9

64Rekenkunde: delers en priemgetallen

Rekenkunde bestudeert gehele getallen en hoe ze elkaar delen. Haar centrale personages zijn de priemgetallen, de bouwstenen waaruit elk geheel getal door vermenigvuldiging wordt samengesteld. Het hoofdstuk eindigt met de grootste gemene deler, het juiste gereedschap om breuken eens en voor altijd te vereenvoudigen. Dit verhaal gaat verder, veel verder, in het High School-volume en daarbuiten.

64.1 Delers en veelvouden

Definitie 64.1 (Deler, veelvoud)

Laat $a$ en $b$ positieve gehele getallen zijn. We zeggen dat $b$ deelt $a$ (of dat $b$ een deler van $a$ is, of dat $a$ een veelvoud van $b$ is) wanneer $a = b \times k$ voor een geheel getal $k$ — dat wil zeggen, wanneer de deling van $a$ door $b$ rest $0$ laat.

Voorbeeld 64.2

De delers van $24$ zijn $1, 2, 3, 4, 6, 8, 12, 24$ — ze komen in paren waarvan het product $24$ is: $(1,24)$ , $(2,12)$ , $(3,8)$ , $(4,6)$ . De veelvouden van $7$ zijn $7, 14, 21, 28, \dots$

Propositie 64.3 (Deelbaarheidsregels)

Een geheel getal is deelbaar:

door $2$ wanneer zijn laatste cijfer even 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$ (resp. $9$ ) wanneer de som van zijn cijfers deelbaar is door $3$ (resp. $9$ );
door $4$ wanneer zijn laatste twee cijfers een getal vormen dat deelbaar is door $4$ .

Bewijs. Toegegeven op dit niveau. ∎

Voorbeeld 64.4

$7\,215$ eindigt op $5$ : deelbaar door $5$ . Zijn cijfersom is $7 + 2 + 1 + 5 = 15$ , deelbaar door $3$ maar niet door $9$ : dus is $7\,215$ deelbaar door $3$ , niet door $9$ . Inderdaad $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 $1$ en zichzelf zijn. De priemgetallen onder $30$ zijn

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

Het getal $1$ is geen priemgetal (per conventie), en een geheel getal $\geq 2$ dat niet priem is heet samengesteld.

Stelling 64.6 (Priemfactorisatie)

Elk geheel getal $\geq 2$ is een product van priemgetallen, en deze factorisatie is uniek op de volgorde van de factoren na.

Bewijs. Toegegeven op dit niveau. ∎

Methode 64.7 (Een geheel getal ontbinden)

Deel door het kleinst mogelijke priemgetal, herhaaldelijk, tot je $1$ bereikt:

probeer $2$ zolang het getal even is;
probeer daarna $3$ , dan $5$ , dan $7$ , … (alleen priemgetallen);
stop wanneer het quotiënt $1$ is; verzamel de factoren met exponenten.

Het volstaat priemgetallen $p$ te proberen met $p^2$ niet groter dan het huidige getal: als geen enkele deelt, 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,

dus

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

De factorenboom van 360: elke stap splitst de kleinste priemfactor af (in rood). De rode bladeren en de finale 5 lezen: 360 = 23 × 32 × 5. — De factorenboom van $360$ : elke stap splitst de kleinste priemfactor af (in rood). De rode bladeren en de finale $5$ lezen: $360 = 2^3 \times 3^2 \times 5$ .

Stelling 64.9 (Euclides)

Er zijn oneindig veel priemgetallen.

Bewijs. Stel dat er er maar eindig veel waren, zeg $p_1, p_2, \dots, p_k$ , en beschouw

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

Delen van $N$ door eender welke $p_i$ laat rest $1$ , dus geen $p_i$ deelt $N$ . Maar $N \geq 2$ heeft minstens één priemdeler (Stelling 64.6) — een priemgetal dat niet op onze lijst staat. Tegenspraak: geen 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$ , genoteerd $\gcd(a, b)$ of $\mathrm{ggd}(a, b)$ , is het grootste gehele getal dat beide deelt. Wanneer $\gcd(a, b) = 1$ , heten de gehele getallen onderling ondeelbaar: ze delen geen deler behalve $1$ .

Voorbeeld 64.11

Delers van $18$ : $1, 2, 3, 6, 9, 18$ . Delers van $24$ : $1, 2, 3, 4, 6, 8, 12, 24$ . Gemeenschappelijke delers: $1, 2, 3, 6$ ; dus $\gcd(18, 24) = 6$ . De gehele getallen $15$ en $28$ zijn onderling ondeelbaar.

Propositie 64.12 (ggd uit factorisaties)

De ggd van twee gehele getallen is het product van de priemgetallen die in beide factorisaties voorkomen, elk met de kleinere van zijn twee exponenten.

Bewijs. Toegegeven op dit niveau. ∎

Voorbeeld 64.13

$360 = 2^3 \times 3^2 \times 5$ en $84 = 2^2 \times 3 \times 7$ . Gemeenschappelijke priemgetallen: $2$ (exponenten $3$ en $2$ : houd $2$ ) en $3$ (exponenten $2$ en $1$ : houd $1$ ). Dus

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

Stelling 64.14 (Euclidisch algoritme)

Als $a = bq + r$ de deling van $a$ door $b$ met rest $r$ is, dan

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

Delingen herhalen tot de rest $0$ is, is de ggd van $a$ en $b$ de laatste van-nul-verschillende rest.

Bewijs. Uit $a = bq + r$ : elk geheel getal dat $b$ en $r$ deelt, deelt $bq + r = a$ ; en uit $r = a - bq$ : elk geheel getal dat $a$ en $b$ deelt, deelt $r$ . Dus hebben de paren $(a, b)$ en $(b, r)$ precies dezelfde gemeenschappelijke delers — in het bijzonder dezelfde grootste. Omdat resten strikt dalen, stopt het algoritme, en $\gcd(x, 0) = x$ geeft de laatste van-nul-verschillende rest. ∎

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 van-nul-verschillende rest is $21$ : $\gcd(1071, 462) = 21$ .

Methode 64.16 (Een breuk volledig vereenvoudigen)

Om $\dfrac ab$ in laagste termen te schrijven:

bereken $d = \gcd(a, b)$ , bijv. met het Euclidische algoritme;
deel teller en noemer door $d$ : $\dfrac ab = \dfrac{a \div d}{b \div d}$ ;
de resulterende breuk is onherleidbaar: teller en noemer zijn onderling ondeelbaar.

Voorbeeld 64.17

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

64.4 Oefeningen

Oefening 64.1 ★

Lijst alle delers van $36$ , van $45$ , en van $17$ .

Oplossing

Oplossing van Oefening 64.1.

Delers van $36$ : $1, 2, 3, 4, 6, 9, 12, 18, 36$ . Delers van $45$ : $1, 3, 5, 9, 15, 45$ . Delers van $17$ : alleen $1$ en $17$ ( $17$ is priem).

Oefening 64.2 ★

Bepaal met de deelbaarheidsregels of $2\,346$ deelbaar is door $2$ , door $3$ , door $4$ , door $5$ , door $9$ .

Oplossing

Oplossing van Oefening 64.2.

$2\,346$ eindigt op $6$ : deelbaar door $2$ , niet door $5$ . Cijfersom $2 + 3 + 4 + 6 = 15$ : deelbaar door $3$ , niet door $9$ . Laatste twee cijfers $46$ , en $46 = 4 \times 11 + 2$ is niet deelbaar door $4$ : $2\,346$ is niet deelbaar door $4$ .

Oefening 64.3 ★

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

Oplossing

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? Is $91$ ? Is $143$ ? Motiveer met de stopregel van Methode 64.7.

Oplossing

Oplossing van Oefening 64.4.

$101$ : test de priemgetallen $p$ met $p^2 \leq 101$ , d.w.z. $2, 3, 5, 7$ . Geen deelt $101$ (oneven, cijfersom $2$ , eindigt niet op $0/5$ , $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 gemeenschappelijke delers te lijsten, en uit de priemfactorisaties.

Oplossing

Oplossing van Oefening 64.5.

Gemeenschappelijke delers van $48$ en $60$ : delers van 48 zijn $1, 2, 3, 4, 6, 8, 12, 16, 24, 48$ ; delers 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 $\gcd(48,60) = 12$ .

Via factorisatie: $48 = 2^4 \times 3$ en $60 = 2^2 \times 3 \times 5$ ; gemeenschappelijke priemgetallen met kleinere exponenten: $2^2 \times 3 = 12$ .

Oefening 64.6 ★★

Gebruik het Euclidische algoritme om $\gcd(255, 154)$ te berekenen, daarna $\gcd(1053, 325)$ . Schrijf elke delingsregel.

Oplossing

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 van-nul-verschillende rest: $\gcd(255, 154) = 1$ (ze zijn onderling ondeelbaar).

$\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 $\dfrac{588}{504}$ onherleidbaar. (Bereken de ggd met de methode van je keuze, en deel daarna.)

Oplossing

Oplossing van Oefening 64.7.

Euclidisch algoritme: $588 = 504 \times 1 + 84$ ; $504 = 84 \times 6 + 0$ : $\gcd(588, 504) = 84$ . Dan

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

wat onherleidbaar is.

Oefening 64.8 ★★

Een bloemist heeft $84$ rozen en $126$ tulpen en wil identieke boeketten maken, met alle bloemen, met zoveel boeketten mogelijk. Hoeveel boeketten kan ze maken, en wat bevat elk?

Oplossing

Oplossing van Oefening 64.8.

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

Oefening 64.9 ★★

Twee veerboten vertrekken van dezelfde steiger om 8:00. De ene vertrekt elke $24$ minuten, de andere elke $36$ minuten. Op welk tijdstip vertrekken ze de volgende keer samen? (Zoek het kleinste gemeenschappelijke veelvoud van $24$ en $36$ ; factorisaties helpen.)

Oplossing

Oplossing van Oefening 64.9.

We zoeken het kleinste gemeenschappelijke veelvoud. $24 = 2^3 \times 3$ en $36 = 2^2 \times 3^2$ ; elk priemgetal met de grotere exponent: $\mathrm{kgv} = 2^3 \times 3^2 = 72$ . De veerboten vertrekken de volgende keer samen $72$ minuten na 8:00, om 9:12.

Oefening 64.10 ★★★

Laat $n$ een positief geheel getal zijn.

Toon dat $\gcd(n, n+1) = 1$ (opeenvolgende gehele getallen zijn altijd onderling ondeelbaar).
Leid af dat de breuk $\dfrac{n}{n+1}$ altijd onherleidbaar is.

Oplossing

Oplossing van Oefening 64.10.

1. Elke gemeenschappelijke deler $d$ van $n$ en $n+1$ deelt ook hun verschil $(n+1) - n = 1$ , dus $d = 1$ : $\gcd(n, n+1) = 1$ .

2. Een breuk is onherleidbaar precies wanneer teller en noemer onderling ondeelbaar zijn, wat voor $n$ en $n + 1$ het geval is door deel 1.