Is het algoritme van Euclides sneller dan priemfactorisatie?

Bij kleine getallen zoals $12$ en $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$ en $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$ en $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$ en $\text{GGD}(168, 1260) = 84$, dus de GGD van alle drie is $84$.

Leermiddelen

Algoritme van Euclides

Q: 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.

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.

Gevorderd25 minLes

Delen in Classroom

Werkblad om te printen

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.

Probeer het meteen

Bij het algoritme van Euclides schrijf je

a = q \times b + r

met

0 \le r < b

. Welk paar deel je daarna?

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$ .

Interactieve visualisatie

Grootste vierkanten in een rechthoek: kies een paar

Eerste getalTweede getal

Rechthoek 1071 × 462

Druk op Volgende stap om de grootste vierkanten af te knippen die passen.

Jij bent aan de beurt: typ het quotiënt en de rest van elke regel

Eerste getalTweede getal

Rechthoek 168 × 120

Hoe vaak past 120 in 168, en wat blijft er over?

168 =× 120 +

Interactieve sandbox

Expressiecalculator

Probeer deze:

Geschiedenis

Nog geen berekeningen

Oefenproblemen

18 opgaven

Opgave 1 van 18

Makkelijk

Bij het algoritme van Euclides schrijf je

a = q \times b + r

met

0 \le r < b

. Welk paar deel je daarna?

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

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.

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$

Uitdaging van vandaagEén opgave, drie pogingen

Meer over dit onderwerp

Definitie

Uitgewerkte voorbeelden

Veelgemaakte fouten

Interactieve visualisatie

Interactieve sandbox

Expressiecalculator

Geschiedenis

Oefenproblemen

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)