Toepassingen

Ken je de grootste gemene deler (GGD) van twee getallen? Er bestaat een leuk probleem met kangoeroesprongen op de getallenlijn waar je de GGD goed bij kunt gebruiken.

De GGD van twee getallen a en b is het grootste (gehele) getal u waarvoor geldt a = m · u en b = n · u.
Dit getal kun je vinden door een getal te ontbinden in priemfactoren. Dat doe je door het te delen door de priemgetallen 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, etc., tot het niet meer gaat (en er dus een priemgetal als rest overblijft).
Bijvoorbeeld is 132 = 2² · 3 · 11 en 96 = 2⁵ · 3.
De GGD van 132 en 96 is daarom 2² · 3 = 12.

Een andere manier om de GGD van 132 en 96 te vinden is het algoritme van Euclides.
Euklides toonde al meer dan tweeduizend jaar geleden aan dat elke geheel a te delen is door een kleiner getal b en dat dan a = b · q + r en 0 ≦ x < b.
q heet het quotiënt van a en b en r is de rest die na deling overblijft.
Je kunt deze stelling gebruiken om de GGD van twee getallen te vinden, want
GGD(a,b) = GGD(b,r). (Bewijs dit zelf.)
En dan kun je problemen oplossen als...