Algoritme van Euclides

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)$ en $(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.

Het meetkundige beeld: vierkanten in een rechthoek van 48 bij 18

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$ en $18$: $\frac{48}{6} \times \frac{18}{6} = 8 \times 3$ = $24$ vierkanten met zijde $6$ bedekken hem

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

De aftrekmethode

Bepaal $\text{GGD}(35, 14)$ alleen met aftrekken: trek steeds het kleinste getal af van het grootste.

Trek 14 af van 35: $35 - 14 = 21$ = Nieuw paar $(21, 14)$

Trek nog een keer 14 af: $21 - 14 = 7$ = Nieuw paar $(14, 7)$

Nu is 7 kleiner: trek 7 af: $14 - 7 = 7$ = Nieuw paar $(7, 7)$

Trek nog één keer af: $7 - 7 = 0$ = De getallen stoppen bij $7$

Answer: $\text{GGD}(35, 14) = 7$. Twee keer $14$ aftrekken is hetzelfde als één deling: $35 = 2 \times 14 + 7$. Delen is gewoon een snelle manier voor veel keer aftrekken.

Een klassieker: de GGD van 1071 en 462

Bepaal $\text{GGD}(1071, 462)$ met het algoritme van Euclides.

Deel 1071 door 462: $462 \times 2 = 924$ en $1071 - 924 = 147$ = $1071 = 2 \times 462 + 147$

Vervang het paar door (462, 147) en deel: $147 \times 3 = 441$ en $462 - 441 = 21$ = $462 = 3 \times 147 + 21$

Vervang het paar door (147, 21) en deel: $21 \times 7 = 147$, er blijft niets over = $147 = 7 \times 21 + 0$

Lees de laatste rest af die niet nul is: De rest werd $0$ bij het delen door $21$ = $\text{GGD}(1071, 462) = 21$

Answer: $\text{GGD}(1071, 462) = 21$. Controle: $1071 = 21 \times 51$ en $462 = 21 \times 22$.

Een lastige breuk vereenvoudigen

Vereenvoudig $\frac{391}{667}$ zo ver mogelijk.

Deel 667 door 391: $667 = 1 \times 391 + 276$ = Rest $276$

Deel 391 door 276: $391 = 1 \times 276 + 115$ = Rest $115$

Deel 276 door 115: $276 = 2 \times 115 + 46$ = Rest $46$

Deel 115 door 46 en daarna 46 door 23: $115 = 2 \times 46 + 23$ en $46 = 2 \times 23 + 0$ = $\text{GGD}(391, 667) = 23$

Deel teller en noemer door 23: $\frac{391 \div 23}{667 \div 23} = \frac{17}{29}$ = $\frac{17}{29}$

Answer: $\frac{391}{667} = \frac{17}{29}$. Omdat $17$ en $29$ allebei priemgetallen zijn, kan de breuk niet verder vereenvoudigd worden.

Het kgv uit de GGD

Bepaal $\text{kgv}(84, 120)$ met het algoritme van Euclides.

Deel 120 door 84: $120 = 1 \times 84 + 36$ = Rest $36$

Deel 84 door 36: $84 = 2 \times 36 + 12$ = Rest $12$

Deel 36 door 12: $36 = 3 \times 12 + 0$ = $\text{GGD}(84, 120) = 12$

Gebruik kgv = a × b ÷ GGD: $\frac{84 \times 120}{12} = \frac{10080}{12}$ = $840$

Controleer: $840 \div 84 = 10$ en $840 \div 120 = 7$ = Allebei delen ze $840$

Answer: $\text{kgv}(84, 120) = 840$.

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.

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

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

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

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

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

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

Mistake: $a \times b$ als kgv nemen

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

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.

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.

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.

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

Beeldverhoudingen van schermen

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

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

Algoritme 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

De GGD is de laatste rest die niet nul is, de deler in de laatste regel

Het werkt omdat $\text{GGD}(a, b) = \text{GGD}(b, r)$: beide paren hebben dezelfde gemeenschappelijke delers

Meetkundig knipt het een rechthoek $a \times b$ in zo groot mogelijke vierkanten; de zijde van het laatste vierkant is de GGD

De aftrekmethode trekt steeds opnieuw het kleinste getal af; delen is daarvan de verkorte versie

Je 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$)

Q: Maakt het uit met welk getal ik begin?

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

Q: Is het algoritme van Euclides sneller dan priemfactorisatie?

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

Q: Wat betekent het als het algoritme eindigt met GGD 1?

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

Q: Kan ik het ook voor drie getallen gebruiken?

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

Presentatie afsluiten

Algoritme van Euclides

1 / 14

Getaltheorie / Factoren & Veelvouden

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.

Gevorderd25 min

Gebruik pijltjestoetsen of spatiebalk om te navigeren