Soorten getallen > BewijzenToepassen
De grootste gemeenschappelijke deler van twee getallen is het grootste getal dat beide getallen zonder rest deelt. Euclides vond een manier om de g.g.d. van twee getallen `a` en `b` te vinden. Dit wordt het algoritme van Euclides genoemd. Het gaat als volgt:
-
Noem het grootste van de beide getallen `A` , het andere `B` .
-
Trek `B` net zo vaak van `A` af totdat er `0` overblijft of een getal kleiner dan `B` .
-
Wanneer er `0` overblijft, is `B` de g.g.d.
-
Zo niet, herhaal dan het algoritme met `B` en wat er van `A` over is.
Bekijk in Toepassen hoe het algoritme van Euclides in elkaar zit.
Stel er zijn twee getallen, `a` en `b` , die als g.g.d. het getal `p` hebben.
Bewijs dat uit `a - q * b = r` volgt dat `text(ggd)(a,b)= text(ggd)(b,r)` .
Bereken nu op deze manier `text(ggd)(140, 504)` .
Bereken met behulp van het algoritme van Euclides `text(ggd)(143, 2541)` .
Een kangoeroe springt vanuit `0` over de getallenlijn met sprongen van `39` of `102` naar links of naar rechts. Hoe kan deze kangoeroe weer op `0` uitkomen?