Hoofdstuk 5

Priemgetallen, ggd en kgv

Priemgetallen zijn de bouwstenen van alle gehele getallen — elk getal kan als product van priemgetallen geschreven worden. Die ontleding maakt het mogelijk om de grootste gemene deler en het kleinste gemene veelvoud snel te berekenen, twee begrippen die je voortdurend nodig hebt bij het werken met breuken.

Priemgetallen en samengestelde getallen

Wanneer je een getal deelt door een ander getal en de rest is nul, dan noem je dat tweede getal een deler van het eerste. Elk geheel getal heeft minstens twee delers: 1 en zichzelf. De vraag hoeveel delers een getal heeft, maakt een groot verschil in de wiskunde.

𝒫

Begrip Priemgetal

Een priemgetal is een natuurlijk getal groter dan 1 dat precies twee delers heeft: 1 en zichzelf. Voorbeelden: 2, 3, 5, 7, 11, 13, …

𝒬

Begrip Samengesteld getal

Een samengesteld getal is een natuurlijk getal groter dan 1 dat meer dan twee delers heeft. Het kan dus als product van twee kleinere natuurlijke getallen (beide groter dan 1) geschreven worden. Voorbeelden: 4, 6, 8, 9, 10, 12, …

Bijzonder geval — Het getal 1

Het getal 1 is noch een priemgetal, noch een samengesteld getal. Het heeft slechts één deler (namelijk zichzelf), terwijl een priemgetal er precies twee moet hebben. Door 1 apart te houden, blijft de priemfactorontleding van elk getal uniek.

Priemgetallen tot 50

Er zijn 15 priemgetallen kleiner dan of gelijk aan 50. Het is nuttig om deze te kennen:

2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 · 29 · 31 · 37 · 41 · 43 · 47

Merk op dat 2 het enige even priemgetal is. Alle andere priemgetallen zijn oneven.

De zeef van Eratosthenes

Een elegante methode om alle priemgetallen tot een bepaald getal te vinden is de zeef van Eratosthenes, uitgedacht door de Griekse wiskundige Eratosthenes (ca. 276–194 v.Chr.). Het algoritme werkt als volgt:

Schrijf alle getallen van 2 tot n op.
Begin bij 2 (het kleinste priemgetal). Streep alle veelvouden van 2 door (4, 6, 8, …), maar niet 2 zelf.
Ga naar het volgende niet-doorgstreepte getal (3). Streep alle veelvouden van 3 door (6, 9, 12, …).
Ga naar het volgende niet-doorgestreepte getal (5). Streep alle veelvouden van 5 door.
Herhaal totdat je het kwadraat van het volgende getal de grens ‘n’ overschrijdt.
De overgebleven getallen zijn alle priemgetallen tot en met n.

Zeef van Eratosthenes: getallen 1–50. Goudgele vakjes zijn priemgetallen (15 in totaal). Het getal 1 (schuingedrukt) is noch priem noch samengesteld.

Rekenvoorbeeld

Is 97 een priemgetal?

Bereken de vierkantswortel van 97: √97 ≈ 9,85. We hoeven dus enkel priemgetallen kleiner dan of gelijk aan 9 te testen: 2, 3, 5, 7.
Test op deelbaarheid door 2: 97 is oneven → niet deelbaar door 2.
Test op deelbaarheid door 3: de cijfersom is 9+7 = 16, en 16 is niet deelbaar door 3 → niet deelbaar door 3.
Test op deelbaarheid door 5: 97 eindigt niet op 0 of 5 → niet deelbaar door 5.
Test op deelbaarheid door 7: 97 = 7 × 13 + 6, rest 6 → niet deelbaar door 7.
Geen enkel priemgetal tot √97 deelt 97 → 97 is een priemgetal.

Antwoord: ja, 97 is een priemgetal. Het heeft precies twee delers: 1 en 97.

💡 Denkvraag

Hoeveel priemgetallen zijn er tussen 50 en 100? Welke zijn het? Gebruik de zeef-methode of de deelbaarheidstest. Bestaat er een patroon in de afstand tussen opeenvolgende priemgetallen?

Priemfactorontleding

Een van de meest fundamentele feiten uit de getaltheorie is dat elk geheel getal groter dan 1 op een unieke manier als product van priemgetallen kan worden geschreven. Dit heet de priemfactorontleding of de ontleding in priemfactoren.

Stelling — Hoofdstelling van de rekenkunst

Elk geheel getal groter dan 1 kan op precies één manier geschreven worden als een product van priemgetallen (als we de volgorde van de factoren buiten beschouwing laten). Deze ontleding is dus uniek.

Voorbeelden: 12 = 2² × 3 · 30 = 2 × 3 × 5 · 100 = 2² × 5²

Methode: de factorboom

Een factorboom is een boomvormig schema waarbij je een getal stap voor stap splitst in twee factoren tot alle takken uitkomen op priemgetallen. De priemgetallen aan de “bladeren” van de boom vormen samen de priemfactorontleding.

Factorboom voor 60. Donkerblauwe vakken zijn tussenknopen (samengestelde getallen), terracottacirkels zijn priembladen. Resultaat: 60 = 2 × 2 × 3 × 5 =

2^{2}

× 3 × 5.

We schrijven de priemfactorontleding geordend van klein naar groot, en gebruiken machten voor herhaalde factoren:

Notatie — priemfactorontleding van 60

60 = 2^{2} \times 3 \times 5

Rekenvoorbeeld

Priemfactorontleding van 84

84 is even: 84 = 2 × 42
42 is even: 42 = 2 × 21
21 = 3 × 7 (beide priemgetallen)
Alle factoren zijn nu priemgetallen: 2, 2, 3, 7. Groepeer met machten.

84 = $2^{2} \times 3 \times 7$

Rekenvoorbeeld

Priemfactorontleding van 360

360 = 2 × 180
180 = 2 × 90
90 = 2 × 45
45 = 3 × 15
15 = 3 × 5 (beide priemgetallen)
Priemfactoren: 2, 2, 2, 3, 3, 5. Schrijf als machten: 2³, 3², 5¹.

360 = $2^{3} \times 3^{2} \times 5$

💡 Denkvraag

Stel dat twee leerlingen elk een verschillende factorboom voor 60 tekenen (de een begint met 60 = 4 × 15, de ander met 60 = 6 × 10). Zullen ze tot dezelfde priemfactorontleding komen? Waarom garandeert de hoofdstelling van de rekenkunst dat?

Grootste gemene deler (ggd)

Wanneer je twee getallen hebt, zijn er getallen die beide delen. Het grootste van die gemeenschappelijke delers is bijzonder nuttig, en heeft een eigen naam en notatie.

≃

Begrip Grootste gemene deler — ggd

De grootste gemene deler van twee gehele getallen a en b, genoteerd als ggd(a, b), is het grootste getal dat zowel a als b deelt (rest 0). Andere notaties: gcd(a,b) of pgcd(a,b).

Methode — ggd via priemfactorontleding

ggd (a, b) = product van gemeenschappelijke priemfactoren met minimale macht

Stap voor stap: ontleed beide getallen in priemfactoren, bepaal welke priemgetallen in beide ontledingen voorkomen, en neem voor elk de kleinste macht. Het product van die factoren is de ggd.

Rekenvoorbeeld

Bereken ggd(36, 48)

Ontleed 36: $36 = 2^{2} \times 3^{2}$
Ontleed 48: $48 = 2^{4} \times 3$
Gemeenschappelijke priemfactoren: 2 en 3.
Minimale macht van 2: min(2,4) = 2 → $2^{2}$
Minimale macht van 3: min(2,1) = 1 → 3
ggd = 2² × 3 = 4 × 3 = 12

ggd(36, 48) = 12

Rekenvoorbeeld

Bereken ggd(72, 120)

Ontleed 72: $72 = 2^{3} \times 3^{2}$
Ontleed 120: $120 = 2^{3} \times 3 \times 5$
Gemeenschappelijke priemfactoren: 2 en 3 (5 komt enkel in 120 voor).
Minimale macht van 2: min(3,3) = 3 → $2^{3}$ = 8
Minimale macht van 3: min(2,1) = 1 → 3
ggd = 2³ × 3 = 8 × 3 = 24

ggd(72, 120) = 24

Praktische toepassing

💡 Praktijkprobleem

Je hebt linten van 36 cm en 48 cm. Je wil beide linten in gelijke stukken knippen, zonder afval. Hoe lang zijn de langst mogelijke stukken?

Oplossing: Je zoekt het grootste getal dat zowel 36 als 48 deelt → ggd(36, 48) = 12. De linten kunnen in stukken van 12 cm gesneden worden: het lint van 36 cm geeft 3 stukken, het lint van 48 cm geeft 4 stukken.

Kleinste gemene veelvoud (kgv)

Naast de gemeenschappelijke delers zijn ook gemeenschappelijke veelvouden nuttig. Het kleinste positieve getal dat door twee (of meer) gegeven getallen deelbaar is, heet het kleinste gemene veelvoud.

∞

Begrip Kleinste gemene veelvoud — kgv

Het kleinste gemene veelvoud van twee gehele getallen a en b, genoteerd als kgv(a, b), is het kleinste positieve getal dat zowel door a als door b deelbaar is. Andere notaties: lcm(a,b) of ppcm(a,b).

Methode — kgv via priemfactorontleding

kgv (a, b) = product van alle priemfactoren met maximale macht

Stap voor stap: ontleed beide getallen in priemfactoren, verzamel alle priemgetallen die in minstens één ontleding voorkomen, en neem voor elk de grootste macht. Het product is het kgv.

Verband — ggd en kgv

Voor elk paar positieve gehele getallen a en b geldt:

$ggd (a, b) \times kgv (a, b) = a \times b$

Dit verband is handig: als je één van de twee kent, vind je de andere via deling.

Rekenvoorbeeld

Bereken kgv(12, 18)

Ontleed 12: $12 = 2^{2} \times 3$
Ontleed 18: $18 = 2 \times 3^{2}$
Alle priemfactoren: 2 en 3.
Maximale macht van 2: max(2,1) = 2 → $2^{2}$ = 4
Maximale macht van 3: max(1,2) = 2 → $3^{2}$ = 9
kgv = 2² × 3² = 4 × 9 = 36
Controle via verband: ggd(12,18) × kgv(12,18) = 6 × 36 = 216 = 12 × 18 ✓

kgv(12, 18) = 36

Rekenvoorbeeld

Bereken kgv(15, 25)

Ontleed 15: $15 = 3 \times 5$
Ontleed 25: $25 = 5^{2}$
Alle priemfactoren: 3 en 5.
Maximale macht van 3: max(1,0) = 1 → 3
Maximale macht van 5: max(1,2) = 2 → $5^{2}$ = 25
kgv = 3 × 5² = 3 × 25 = 75
Controle: ggd(15,25) = 5; 5 × 75 = 375 = 15 × 25 ✓

kgv(15, 25) = 75

Praktische toepassing

💡 Praktijkprobleem

Bus A rijdt elke 12 minuten, Bus B elke 18 minuten. Ze vertrekken op hetzelfde moment samen van het eindpunt. Na hoeveel minuten vertrekken ze opnieuw gelijktijdig?

Oplossing: Je zoekt het kleinste getal dat zowel door 12 als door 18 deelbaar is → kgv(12, 18) = 36. Na 36 minuten vertrekken beide bussen opnieuw samen. Op dat moment heeft Bus A 3 ritten gereden (36 ÷ 12) en Bus B 2 ritten (36 ÷ 18).

Toepassingen

De ggd en het kgv zijn niet alleen abstracte begrippen — ze zijn onmisbaar bij het vereenvoudigen van breuken en het optellen van breuken met ongelijke noemers. Je hebt deze technieken al ontmoet in Hoofdstuk 3.

Breuken vereenvoudigen met de ggd

Om een breuk $\frac{a}{b}$ te vereenvoudigen, deel je teller en noemer door hun ggd. De resulterende breuk is volledig vereenvoudigd (in laagste termen) omdat er geen gemeenschappelijke deler meer is groter dan 1.

Rekenvoorbeeld — vereenvoudigen

Vereenvoudig de breuk $\frac{84}{120}$

Ontleed 84: $84 = 2^{2} \times 3 \times 7$
Ontleed 120: $120 = 2^{3} \times 3 \times 5$
ggd(84, 120): gemeenschappelijke factoren zijn 2 en 3.
Min. macht van 2: min(2,3)=2 → $2^{2}$ ; min. macht van 3: min(1,1)=1 → 3.
ggd = 4 × 3 = 12
Deel teller en noemer door 12: $\frac{84}{120} = \frac{84 - : 12}{120 - : 12} = \frac{7}{10}$

$\frac{84}{120} = \frac{7}{10}$ (volledig vereenvoudigd: ggd(7,10)=1)

Breuken optellen met het kgv

Om breuken met ongelijke noemers op te tellen, zoek je een gemeenschappelijke noemer. De kleinst mogelijke gemeenschappelijke noemer is het kgv van de twee noemers. Zo vermijd je onnodige grote getallen.

Rekenvoorbeeld — optellen van breuken

Bereken $\frac{5}{12} + \frac{7}{18}$

Bepaal kgv(12, 18). Uit sectie 4 weten we: kgv(12, 18) = 36. Dit is onze gemeenschappelijke noemer.
Breng $\frac{5}{12}$ op noemer 36: vermenigvuldig teller en noemer met 3 (want 36 ÷ 12 = 3): $\frac{5 \times 3}{12 \times 3} = \frac{15}{36}$
Breng $\frac{7}{18}$ op noemer 36: vermenigvuldig teller en noemer met 2 (want 36 ÷ 18 = 2): $\frac{7 \times 2}{18 \times 2} = \frac{14}{36}$
Tel de gelijknamige breuken op: $\frac{15}{36} + \frac{14}{36} = \frac{29}{36}$
Controleer of de breuk te vereenvoudigen is: ggd(29, 36) = 1 (want 29 is priemgetal) → reeds volledig vereenvoudigd.

$\frac{5}{12} + \frac{7}{18} = \frac{29}{36}$

💡 Denkvraag

Wat zou er mis gaan als je bij het optellen van $\frac{5}{12} + \frac{7}{18}$ een andere gemeenschappelijke noemer zou kiezen, zoals 12 × 18 = 216? Welk extra stapje zou je dan moeten uitvoeren? Probeer het zelf en vergelijk met het resultaat via kgv.

Computationeel denken

De zeef van Eratosthenes uit sectie 1 is meer dan een trucje om priemgetallen te vinden: het is een echt algoritme. Wanneer je nadenkt over hoe je zo’n stappenplan opbouwt, denk je net zoals een programmeur. Dat noemen we computationeel denken: een probleem zo aanpakken dat je het stap voor stap, en desnoods door een computer, kunt laten oplossen.

𝒫

Begrip Algoritme

Een algoritme is een reeks duidelijke instructies of een stappenplan om een taak uit te voeren of een probleem op te lossen. Een goed algoritme is eindig (het stopt ooit) en eenduidig (bij elke stap is precies duidelijk wat je moet doen).

Vier denkstappen

Computationeel denken steunt op vier principes. We bekijken ze meteen aan de hand van de zeef van Eratosthenes.

𝒬

Begrip Decompositie

Decompositie betekent een groot probleem opdelen in kleinere, eenvoudigere deelproblemen. “Vind alle priemgetallen tot 50” splits je in: getallen opschrijven → veelvouden van 2 wegstrepen → veelvouden van 3 wegstrepen → … → aflezen wat overblijft.

𝒫

Begrip Patroonherkenning

Patroonherkenning is gelijkenissen ontdekken zodat je dezelfde aanpak kunt hergebruiken. Het wegstrepen van veelvouden van 2 verloopt net zoals dat van veelvouden van 3 of 5 — enkel het getal verandert. Je hoeft de stap dus niet telkens opnieuw te bedenken.

𝒬

Begrip Abstractie

Abstractie betekent overtollige details weglaten en tot de kern komen. Of een vakje nu rood of doorstreept is, doet er niet toe: het enige wat telt, is “is dit getal al een veelvoud van een eerder priemgetal of niet?”

Het algoritme als stroomdiagram

Een stroomdiagram (of flowchart) tekent een algoritme als een schema van vakjes en pijlen. Een ruit stelt een ja/nee-vraag voor, een rechthoek een handeling. Hieronder zie je de kern van de zeef van Eratosthenes:

Stroomdiagram van de zeef van Eratosthenes. De ruit is een ja/nee-vraag; de pijl die terugloopt vormt een lus die zich herhaalt tot p×p groter wordt dan n.

Hetzelfde in pseudocode

Een algoritme kun je ook in pseudocode opschrijven: een soort tussentaal tussen gewone taal en een echte programmeertaal. Ze is bedoeld voor mensen, niet voor de computer, maar ligt er al dicht bij.

Pseudocode — Zeef van Eratosthenes

Vind alle priemgetallen tot en met n.

schrijf de getallen 2 tot en met n op
p ← 2
ZOLANG p × p ≤ n:
    streep alle veelvouden van p weg (maar niet p zelf)
    p ← eerstvolgende getal dat nog niet is doorstreept
de overgebleven getallen zijn de priemgetallen

Debuggen: fouten opsporen

Een algoritme bedenken lukt zelden in één keer foutloos. Debuggen is het opsporen en verbeteren van fouten (“bugs”) in een algoritme. Je test het stap voor stap met een eenvoudig voorbeeld en kijkt waar het misloopt.

Rekenvoorbeeld — Een bug zoeken

Een leerling schreef: “streep p zelf ook weg”. Waar loopt het mis?

Test met n = 10. Stap 1 kiest p = 2.
De foute regel streept ook 2 zelf weg, naast 4, 6, 8, 10.
Na afloop ontbreekt 2 bij de overgebleven getallen, terwijl 2 wél een priemgetal is.
De fout zit in de instructie: je mag de veelvouden wegstrepen, maar p zelf moet blijven staan.
Verbeter de regel naar “streep alle veelvouden van p weg, maar niet p zelf” en test opnieuw → nu klopt het.

Antwoord: de bug zat in het per ongeluk wegstrepen van p zelf. Door met een klein voorbeeld te testen, vind je zo’n fout snel.

💡 Denkvraag

Schrijf zelf een algoritme (in pseudocode of als stroomdiagram) dat nagaat of een gegeven getal even of oneven is. Welke deelstappen zitten erin? Welke vraag (ja/nee) staat centraal?

Oefeningen

Oefening 1

Priemgetallen en samengestelde getallen herkennen

Geef voor elk van de volgende getallen aan of het een priemgetal, een samengesteld getal, of geen van beide is. Verklaar telkens kort je redenering.

Tip: test deelbaarheid door priemgetallen tot de vierkantswortel van het getal. √51 ≈ 7,1; √91 ≈ 9,5; √121 = 11.

Oefening 2

Priemfactorontleding

Schrijf elk van de volgende getallen als product van priemfactoren. Gebruik machten waar van toepassing.

Tip: teken een factorboom. Controleer je antwoord door de factoren terug te vermenigvuldigen.

Oefening 3

Grootste gemene deler berekenen

Bereken de ggd van elk van de volgende paren via priemfactorontleding. Toon je werkwijze.

ggd(24, 36)
ggd(45, 75)
ggd(84, 126)
ggd(100, 360)

Oefening 4

Kleinste gemene veelvoud berekenen

Bereken het kgv van elk van de volgende paren via priemfactorontleding. Toon je werkwijze en controleer via het verband ggd × kgv = a × b.

kgv(8, 12)
kgv(14, 21)
kgv(16, 24)
kgv(45, 60)

Oefening 5

Breuken vereenvoudigen

Vereenvoudig elke breuk volledig. Gebruik de ggd van teller en noemer.

$\frac{36}{48}$
$\frac{72}{120}$
$\frac{126}{210}$
$\frac{45}{135}$

Tip: controleer je antwoord door te kijken of ggd(teller, noemer) = 1. Als dat zo is, is de breuk volledig vereenvoudigd.

Oefening 6

Planningsrooster — kgv in een praktijkcontext

Een bakker maakt elke 8 dagen een nieuwe portie witbrood en elke 12 dagen een nieuwe portie roggebrood. Vandaag maakt hij beide soorten tegelijkertijd.

Na hoeveel dagen maakt hij beide soorten opnieuw tegelijkertijd? Gebruik het kgv.
Hoeveel keer maakt hij in die periode witbrood? Hoeveel keer roggebrood?
Stel dat er ook een derde soort brood is die hij elke 15 dagen maakt (en die hij vandaag ook maakt). Na hoeveel dagen maakt hij alle drie de soorten opnieuw tegelijkertijd? Bereken kgv(8, 12, 15).

Tip: voor kgv van drie getallen: bereken eerst kgv(8,12), en bereken dan kgv(dat resultaat, 15).

Priemgetallen,ggd en kgv

Priemgetallen, ggd en kgv

Priemgetallen en samengestelde getallen

Priemgetallen tot 50

De zeef van Eratosthenes

Priemfactorontleding

Methode: de factorboom

Grootste gemene deler (ggd)

Praktische toepassing

Kleinste gemene veelvoud (kgv)

Praktische toepassing

Toepassingen

Breuken vereenvoudigen met de ggd

Breuken optellen met het kgv

Computationeel denken

Vier denkstappen

Het algoritme als stroomdiagram

Hetzelfde in pseudocode

Debuggen: fouten opsporen

Oefeningen

Samenvatting

Priemgetallen,
ggd en kgv