] >
Het is duidelijk hoe je in principe van twee getallen en de ggd kunt uitrekenen: eerst bepaal je de delers van , en ook die van ; vervolgens bepaal je hun gemene delers en tenslotte neem je de grootste. Dat is zeer omslachtig, zeker bij grote getallen. Er is echter een snelle methode. Deze was al bekend bij de Grieken. Eerst een lemma.
Bewijs. Een gemene deler van en is ook een gemene deler van en . En omgekeerd. Dus hebben enerzijds en en anderzijds en dezelfde gemene delers. In het bijzonder hebben ze ook dezelfde grootste gemene deler. □
7.28 Algoritme (Euclides). Het bepalen van de grootste gemene deler van is, als , volgens Lemma 7.27 met behulp van delen met rest terug te voeren tot het bepalen van de grootste gemene deler van en , waarbij . Zolang het tweede getal niet nul is, is het bepalen van de grootste gemene deler terug te voeren tot het bepalen van de grootste gemene deler van een tweetal getallen met een kleiner tweede getal. Is het tweede getal 0, dan is het eerste getal de grootste gemene deler.
Laten en natuurlijke getallen zijn. Als , dan kunnen we delen met rest toepassen:
als , dan opnieuw delen met rest
als , dan opnieuw delen met rest
Zolang de rest is, passen we delen met rest toe. De resten vormen een strikt dalende rij van natuurlijke getallen: is een rest , dan krijgen we bij de volgende stap een nieuwe rest die kleiner is. Dit proces houdt op zodra een rest optreedt:
De grootste gemene deler van en is dan (= de laatste rest die van verschilt). Dit algoritme is zeer snel.
In het algoritme wordt met twee getallen begonnen en deze worden vervangen door een tweetal, waarvan het eerste getal het laatste is van het vorige tweetal. Je krijgt zo een rij van getallen, waarvan het laatste is en het voorlaatste de grootste gemene deler:
1665 | 987 | 687 | 291 | 105 | 81 | 24 | 9 | 6 | 3 | 0 |
We beginnen een nieuw pythonmodule, arithmetics.py. Daarin maken we gebruik van de functies en methoden in Python voor het datatype integer. We beperken ons dus niet tot succ zoals we eerder deden.
Python gaat automatisch over op het datatype long integer als de getallen te groot worden. Er is geen grens aan de grootte van deze getallen anders dan de grens die door de fysieke eigenschappen van de computer wordt gesteld.
Herhaald delen met rest kun je met Python uiteraard eenvoudig programmeren. Je begint met het tweetal en als , dan pas je delen met rest toe: . Het tweetal wordt dan vervangen door . Daar ga je mee door totdat het tweede getal van het tweetal is. Het eerste is dan de grootste gemene deler. Dit wordt bereikt met de functie gcd in het bestand arithmetics.py.
We representeren rationale getallen door -tuples van gehele getallen. De optelling en de vermenigvuldiging kunnen in Python makkelijk beschreven worden. Door de uitkomsten te vereenvoudigen worden de getallen minder snel groot.