Docentenhandleiding: Algoritme van Euclides

Vind de grootste gemene deler van twee getallen door herhaald delen met rest, en gebruik die om breuken te vereenvoudigen en het kgv te bepalen.

Les presenteren Delen in Classroom Studentpagina bekijken

Gebruik deze les in de klas

Gratis, leerlingen hebben geen account nodig.

Delen met leerlingen

Leerlingen openen de les en oefenen met directe feedback.

Werkblad om te printen

Alle oefenopgaven op papier, met een apart antwoordblad.

Werkblad Antwoorden

Klassenquiz

10 vragen over Factoren & Veelvouden. Leerlingen doen mee met een naam, jij ziet alle scores.

Voor docenten

Leerdoelen

Een deling met rest schrijven in de vorm $a = q \times b + r$ met $0 \le r < b$
De GGD van twee getallen bepalen met het algoritme van Euclides en met de aftrekmethode
Uitleggen waarom $\text{GGD}(a, b) = \text{GGD}(b, r)$ en het algoritme koppelen aan het knippen van een rechthoek in vierkanten
De GGD gebruiken om breuken te vereenvoudigen en $\text{kgv}(a, b) = \frac{a \times b}{\text{GGD}(a, b)}$ te berekenen
Bepalen of twee getallen relatief priem zijn en het algoritme vergelijken met priemfactorisatie

Vereisten

• Grootste gemene deler (GGD): bepalen door delers op te sommen en met priemfactorisatie
• Kleinste gemene veelvoud (kgv) en wat het betekent
• Priemfactorisatie, priemgetallen en samengestelde getallen
• Natuurlijke getallen delen met rest

Discussiestarters

1. Waarom stopt het algoritme altijd? Wat gebeurt er bij elke stap met de getallen?
2. Als $d$ de getallen $48$ en $18$ deelt, waarom moet het dan ook $48 - 2 \times 18 = 12$ delen?
3. Wanneer zou je liever priemfactorisatie gebruiken, en wanneer het algoritme van Euclides?
4. Waarom hebben buurgetallen uit de rij van Fibonacci, zoals $144$ en $89$ , zoveel stappen nodig?
5. Hoe laat het knippen van een rechthoek in vierkanten dezelfde stappen zien als de delingen?

Veelvoorkomende misvattingen

De GGD is het laatst opgeschreven getal, vaak de rest $0$ of een quotiënt

Herstel: Markeer q en r in elke regel met verschillende kleuren. Omcirkel de deler van de regel met rest $0$ en controleer dat die beide begingetallen deelt.

Na de eerste deling ga je verder met het oorspronkelijke grote getal

Herstel: Gebruik het rechthoekbeeld: zodra de vierkanten eraf geknipt zijn, is de lange kant weg en blijft alleen de rechthoek b bij r over.

Het algoritme is een truc die toevallig werkt

Herstel: Laat met $48$ , $18$ en $12$ zien dat elke gemeenschappelijke deler van $48$ en $18$ ook $12$ deelt, en dat elke gemeenschappelijke deler van $18$ en $12$ ook $48$ deelt. Schrijf beide verzamelingen gemeenschappelijke delers op: ze zijn gelijk.

DifferentiatieIdeeën

Voor leerlingen met moeite:

• Begin met de aftrekmethode bij kleine paren zoals (35, 14) voordat je gaat delen
• Gebruik rechthoeken van ruitjespapier en knip de vierkanten echt uit
• Geef een tabel met de kolommen a, b, q, r om regel voor regel in te vullen

Voor leerlingen op niveau:

• Pas het algoritme toe op paren van drie en vier cijfers zoals (1071, 462)
• Vereenvoudig breuken zoals $\frac{391}{667}$ met de GGD
• Bereken kgv's met $\frac{a \times b}{\text{GGD}(a, b)}$ en controleer ze

Voor gevorderde leerlingen:

• Bewijs in het algemeen dat $\text{GGD}(a, b) = \text{GGD}(b, r)$
• Onderzoek waarom buurgetallen uit de rij van Fibonacci de meeste stappen vragen
• Verken het uitgebreide algoritme van Euclides: schrijf $\text{GGD}(a, b)$ als $x \times a + y \times b$

Standaarduitlijning

6.NS.B.4 (CCSS.MATH.CONTENT.6.NS.B.4)
De grootste gemene deler en het kleinste gemene veelvoud van twee natuurlijke getallen bepalen
6.NS.B.2 (CCSS.MATH.CONTENT.6.NS.B.2)
Getallen van meerdere cijfers vlot delen met het standaardalgoritme (staartdeling)
MP.7 (CCSS.MATH.PRACTICE.MP7)
Structuur zoeken en gebruiken

Lesbronnen

visualVan rechthoek naar vierkanten
Interactieve weergave die een rechthoek a bij b in de grootste vierkanten knipt en daarbij elke regel a = q × b + r opschrijft
activityVierkanten op ruitjespapier
Leerlingen tekenen een rechthoek van 48 bij 18 op ruitjespapier en knippen met een schaar de grootste vierkanten eraf tot alleen gelijke vierkanten overblijven
gameGGD-race
Het ene team gebruikt priemfactorisatie, het andere het algoritme van Euclides, bij paren zoals (1071, 462) en (391, 667)
worksheetOefenen met Euclides-regels
Quotiënten en resten invullen, daarna breuken vereenvoudigen en kgv's uit de GGD berekenen

Lesinhoud

Alles wat leerlingen zien: definitie, voorbeelden, veelgemaakte fouten, toepassingen. Tik om te openen.

Definitie

Het algoritme van Euclides is een snelle manier om de grootste gemene deler (GGD) van twee natuurlijke getallen te vinden, zonder delers op te sommen of factorbomen te tekenen.

Deel het grootste getal

a

door het kleinste getal

b

en schrijf het resultaat als deling met rest:

a = q \times b + r, \quad 0 \le r < b

Hierbij is

q

het quotiënt en

r

de rest. **Vervang daarna het paar

(a, b)

door

(b, r)

** en deel opnieuw. Herhaal dit tot de rest

0

is. De laatste rest die niet nul is (de deler in de laatste regel) is de GGD.

Voorbeeld:

\text{GGD}(48, 18)

$48 = 2 \times 18 + 12$
$18 = 1 \times 12 + 6$
$12 = 2 \times 6 + 0$

De rest is

0

, dus

\text{GGD}(48, 18) = 6

Waarom het werkt: als een getal

d

zowel

a

als

b

deelt, dan deelt het ook

r = a - q \times b

. En als

d

zowel

b

als

r

deelt, dan deelt het ook

a = q \times b + r

. De paren

(a, b)

(b, r)

hebben dus precies dezelfde gemeenschappelijke delers, en daarom dezelfde GGD:

\text{GGD}(a, b) = \text{GGD}(b, r)

De getallen worden bij elke stap kleiner, dus het algoritme stopt altijd.

Uitgewerkte voorbeelden

Een rechthoek is

48

bij

18

. Knip steeds de grootst mogelijke vierkanten eraf. Wat is de zijde van de vierkanten die aan het eind precies passen?

Knip vierkanten met zijde 18 van de lange kant

Er passen twee vierkanten

18 \times 18

, er blijft

12

over:

48 = 2 \times 18 + 12

→ Overgebleven rechthoek

18 \times 12

Knip vierkanten met zijde 12 van de rest

Er past één vierkant

12 \times 12

, er blijft

6

over:

18 = 1 \times 12 + 6

→ Overgebleven rechthoek

12 \times 6

Knip vierkanten met zijde 6

Er passen precies twee vierkanten

6 \times 6

12 = 2 \times 6 + 0

→ Er blijft niets over

Bedek de hele rechthoek met het laatste vierkant

6

deelt

48

18

\frac{48}{6} \times \frac{18}{6} = 8 \times 3

→

24

vierkanten met zijde

6

bedekken hem

Antwoord: De vierkanten met zijde $6$ passen precies, dus $\text{GGD}(48, 18) = 6$ . Elke knip is één regel van het algoritme.

Veelgemaakte fouten

Het oude grote getal houden: na $48 = 2 \times 18 + 12$ verdergaan met $48$ en $12$

Waarom het fout is: Het algoritme werkt omdat $\text{GGD}(a, b) = \text{GGD}(b, r)$ . Het getal $a$ is na de eerste deling niet meer nodig.

Correct: Het volgende paar is $(18, 12)$ : de oude deler en de rest. Dus $18 = 1 \times 12 + 6$ .

$0$ of het laatste quotiënt als GGD geven

Waarom het fout is: De laatste regel heeft rest $0$ , en dat zegt alleen dat je kunt stoppen. Het quotiënt telt hoeveel vierkanten er passen, het is geen gemeenschappelijke deler.

Correct: De GGD is de laatste rest die niet nul is, de deler in de laatste regel. Bij $12 = 2 \times 6 + 0$ is dat $6$ .

Een te grote rest opschrijven, zoals $1071 = 1 \times 462 + 609$

Waarom het fout is: De gelijkheid klopt, maar $609 > 462$ , dus $462$ past er nog een keer in. De rest moet kleiner zijn dan de deler.

Correct: Neem het grootst mogelijke quotiënt: $1071 = 2 \times 462 + 147$ met $147 < 462$ .

$a \times b$ als kgv nemen

Waarom het fout is: $a \times b$ is altijd een gemeenschappelijk veelvoud, maar meestal niet het kleinste: $84 \times 120 = 10080$ telt de gemeenschappelijke deler $12$ dubbel.

Correct: Deel door de GGD: $\text{kgv}(84, 120) = \frac{84 \times 120}{12} = 840$ .

Waarom het belangrijk is

Het algoritme van Euclides is meer dan 2300 jaar oud (Euclides schreef het rond 300 v.Chr. op) en het is nog steeds een van de meest gebruikte algoritmes ter wereld:

Grote getallen: $1071$ of $391$ ontbinden in priemfactoren gaat traag, maar drie of vier delingen geven meteen de GGD. Bij getallen van honderden cijfers is priemfactorisatie praktisch onmogelijk, terwijl het algoritme van Euclides hooguit een paar duizend snelle stappen nodig heeft.
Breuken: om $\frac{391}{667}$ te vereenvoudigen heb je $\text{GGD}(391, 667) = 23$ nodig. Door te ontbinden zie je dat moeilijk, met het algoritme gaat het snel.
kgv: zodra je de GGD kent, geldt $\text{kgv}(a, b) = \frac{a \times b}{\text{GGD}(a, b)}$ . Eén algoritme geeft je dus allebei.
Tegels, tandwielen en schermen: de grootste vierkante tegel voor een vloer, wanneer twee tandwielen weer gelijk staan en waarom een scherm van $1920 \times 1080$ de verhouding $16:9$ heeft, komen allemaal neer op de GGD.
Veiligheid op internet: versleutelingssystemen zoals RSA gebruiken een uitgebreide versie van dit algoritme elke keer dat je een beveiligde website opent.

Toepassingen in de echte wereld

Een vloer betegelen met de grootste vierkante tegels

Een tegelzetter wil een rechthoekige vloer bedekken met gelijke vierkante tegels zonder er een te zagen. De grootst mogelijke zijde is de GGD van de twee lengtes.

Voorbeeld:

Een paneel van $48$ cm bij $18$ cm wordt precies bedekt door vierkanten van $6$ cm: $\text{GGD}(48, 18) = 6$ , dus $8 \times 3 = 24$ tegels.

1Probeer het zelf

De vloer van een gang is $168$ cm bij $120$ cm. Die moet bedekt worden met gelijke vierkante tegels, zonder zagen en zonder gaten.

Wat is de zijde in cm van de grootste vierkante tegel die past?

Stap 1: Schrijf de wiskundige uitdrukking

Bepaal $\text{GGD}(168, 120)$ met het algoritme van Euclides:

Tandwielen en terugkerende cycli

Als twee tandwielen samen draaien, raken dezelfde twee tanden elkaar pas weer na een aantal tanden dat gelijk is aan het kgv van de aantallen tanden. Het algoritme van Euclides geeft de GGD, en daaruit volgt het kgv.

Voorbeeld:

Tandwielen met $18$ en $48$ tanden: $\text{GGD} = 6$ , dus dezelfde tanden raken elkaar weer na $\frac{18 \times 48}{6} = 144$ tanden.

2Probeer het zelf

Een fietstandwiel heeft $84$ tanden en een klein tandwiel heeft $36$ tanden. Twee gemarkeerde tanden raken elkaar nu.

Na hoeveel tanden raken de twee gemarkeerde tanden elkaar weer?

Stap 1: Schrijf de wiskundige uitdrukking

Bepaal $\text{kgv}(84, 36) = \frac{84 \times 36}{\text{GGD}(84, 36)}$ :

Beeldverhoudingen van schermen

Een resolutie als $1920 \times 1080$ wordt een beeldverhouding door beide getallen te delen door hun GGD.

Voorbeeld:

$1280 \times 1024$ : $\text{GGD}(1280, 1024) = 256$ , dus de verhouding is $5:4$ .

3Probeer het zelf

Een monitor heeft $1920$ bij $1080$ pixels. Voor de beeldverhouding deel je beide getallen door hun GGD.

Wat is $\text{GGD}(1920, 1080)$ ?

Stap 1: Schrijf de wiskundige uitdrukking

Pas het algoritme van Euclides toe op $1920$ en $1080$ :

Belangrijke punten

1Algoritme van Euclides: deel $a$ door $b$ als $a = q \times b + r$ met $0 \le r < b$ en vervang $(a, b)$ door $(b, r)$ tot de rest $0$ is
2De GGD is de laatste rest die niet nul is, de deler in de laatste regel
3Het werkt omdat $\text{GGD}(a, b) = \text{GGD}(b, r)$ : beide paren hebben dezelfde gemeenschappelijke delers
4Meetkundig knipt het een rechthoek $a \times b$ in zo groot mogelijke vierkanten; de zijde van het laatste vierkant is de GGD
5De aftrekmethode trekt steeds opnieuw het kleinste getal af; delen is daarvan de verkorte versie
6Je gebruikt het om breuken te vereenvoudigen, om $\text{kgv}(a, b) = \frac{a \times b}{\text{GGD}(a, b)}$ te berekenen en om te testen of twee getallen relatief priem zijn (GGD $= 1$ )

Veelgestelde vragen

Maakt het uit met welk getal ik begin?

Nee. Als je met het kleinste getal voorop begint, is de eerste regel bijvoorbeeld

18 = 0 \times 48 + 18

, en die verwisselt alleen de twee getallen. Beginnen met het grootste getal bespaart je die stap.

Is het algoritme van Euclides sneller dan priemfactorisatie?

Bij kleine getallen zoals

12

18

zijn beide snel. Bij grote getallen wel, en ruim: je hoeft geen enkel priemgetal te vinden.

\text{GGD}(1071, 462)

kost drie delingen, terwijl ontbinden

1071 = 3^2 \times 7 \times 17

462 = 2 \times 3 \times 7 \times 11

vraagt.

Wat betekent het als het algoritme eindigt met GGD 1?

Dan zijn de twee getallen relatief priem (onderling ondeelbaar): ze hebben geen gemeenschappelijke deler behalve

1

. Buurgetallen uit de rij van Fibonacci, zoals

144

89

, zijn altijd relatief priem, en bij hen heeft het algoritme voor hun grootte de meeste stappen nodig.

Kan ik het ook voor drie getallen gebruiken?

Ja, steeds twee tegelijk:

\text{GGD}(a, b, c) = \text{GGD}(\text{GGD}(a, b), c)

. Bijvoorbeeld

\text{GGD}(840, 1176) = 168

\text{GGD}(168, 1260) = 84

, dus de GGD van alle drie is

84

Woordenlijst

Algoritme van Euclides: Methode voor de GGD van twee getallen: delen met rest, het paar vervangen door (deler, rest) en herhalen tot de rest $0$ is
Deling met rest: De schrijfwijze $a = q \times b + r$ met $0 \le r < b$ , bijvoorbeeld $1071 = 2 \times 462 + 147$
Quotiënt: Het aantal $q$ keer dat $b$ helemaal in $a$ past
Rest: Het getal $r$ dat na het delen overblijft, altijd kleiner dan de deler
Relatief priem (onderling ondeelbaar): Twee getallen waarvan de GGD $1$ is, zoals $144$ en $89$
Kleinste gemene veelvoud (kgv): Het kleinste positieve getal dat door beide getallen deelbaar is; $\text{kgv}(a, b) = \frac{a \times b}{\text{GGD}(a, b)}$

Formulekaart

Deling met rest

a = q \times b + r, \quad 0 \le r < b

Eén regel van het algoritme: $q$ is het quotiënt, $r$ de rest

Kernstap

\text{GGD}(a, b) = \text{GGD}(b, r)

Vervang het paar door (deler, rest) en herhaal tot $r = 0$

kgv uit de GGD

\text{kgv}(a, b) = \frac{a \times b}{\text{GGD}(a, b)}

Vermenigvuldig de getallen en deel door hun GGD

Relatief priem

\text{GGD}(a, b) = 1

De getallen hebben geen gemeenschappelijke deler behalve $1$

Meer over dit onderwerp

Docentenhandleiding: Algoritme van Euclides

Gebruik deze les in de klas

Voor docenten

Voor leerlingen met moeite:

Voor leerlingen op niveau:

Voor gevorderde leerlingen:

Lesinhoud

Definitie

Uitgewerkte voorbeelden

Veelgemaakte fouten

Waarom het belangrijk is

Toepassingen in de echte wereld

Een vloer betegelen met de grootste vierkante tegels

Tandwielen en terugkerende cycli

Beeldverhoudingen van schermen

Belangrijke punten

Veelgestelde vragen

Woordenlijst

Formulekaart

Deling met rest

Kernstap

kgv uit de GGD

Relatief priem

Meer over dit onderwerp

Delers en veelvouden

Priemfactorisatie

Priemgetallen en samengestelde getallen

Grootste Gemene Deler (GGD)