Toepassingen

Een kangoeroe zit bij 0 op de getallenlijn. Hij kan sprongen maken van 132 en 96 eenheden zowel in positieve als in negatieve richting.
Welke getallen kan hij bereiken?

Antwoord

Als je even goed nadenkt ontdek je dat het hierbij gaat om de GGD van 132 en 96.
Je kunt alle twaalfvouden bereiken.
Maar hoe zie je dat nu in?

Met het algoritme van Euklides bepaal je zo GGD(132,96):
132 = 96 · 1 + 36    GGD(132,96) = GGD(96,36)
  96 = 36 · 2 + 24    GGD(132,96) = GGD(36,24)
  36 = 24 · 1 + 12    GGD(132,96) = GGD(24,12)
  24 = 12 · 2 + 0      GGD(132,96) = GGD(12,0)
Conclusie: GGD(132,96) = 12.

Je laat zien hoe je 12 bereikt met sprongen van 132 en 96 door uit het voorgaande te halen:
12 = 36 – 24 · 1 = 36 – (96 – 36 · 2) · 1 = 
    = (132 – 96 · 1) – (96 – (132 – 96 · 1) · 2) · 1 = 3 · 132 – 4 · 96.

Conclusie: je bereikt 12 door 3 sprongen van 132 en 4 van –96 te maken. Alle veelvouden van 12 bereik je nu ook gemakkelijk.