Het Euclidische algoritme voor grote getallen, theorie

Een methode voor het berekenen (vinden) van de grootste gemene delers (ggd) van grote getallen

Voor grote getallen is het ontbinden in priemfactoren langdurig en moeilijk. Als we voor zulke grote getallen de grootste gemene deler (ggd) zouden moeten berekenen, dan zou een methode die niet gebaseerd is op het ontbinden in priemfactoren van de getallen meer dan welkom zijn. Het Euclidische algoritme is zo'n methode om de ggd te berekenen.

Dit algoritme begint met het delen van de getallen en het opnemen van de rest van de bewerking.
Als 'a' en 'b' de twee positieve gehele getallen zijn, 'a' >= 'b'.
Deel 'a' door 'b' en verkrijg de rest, 'r'.
Als 'r' = 0, STOP. 'b' is de ggd van 'a' en 'b'.
Anders: vervang ('a' door 'b') en ('b' door 'r'). Keer terug naar de stap hierboven.

[1] Begin met het delen van het grotere getal door het kleinere:
53.667 ÷ 25.527 = 2 en de Rest = 2.613 => 53.667 = 25.527 × 2 + 2.613
[2] Deel vervolgens het kleinere getal door de rest van de bovenstaande bewerking:
25.527 ÷ 2.613 = 9 en de Rest = 2.010 => 25.527 = 2.613 × 9 + 2.010
[3] Deel de rest van de eerste bewerking door de rest van de tweede bewerking:
2.613 ÷ 2.010 = 1 en de Rest = 603 => 2.613 = 2.010 × 1 + 603
[4] Deel de rest van de tweede bewerking door de rest van de derde bewerking:
2.010 ÷ 603 = 3 en de Rest = 201 => 2.010 = 603 × 3 + 201
[5] Deel de rest van de derde bewerking door de rest van de vierde bewerking:
603 ÷ 201 = 3 en de Rest = 0 => 603 = 201 × 3
Bij deze stap is de rest nul, dus stoppen we: 201 is het getal dat we zochten.
Ten slotte:
201 is de laatste niet-nul rest. Dit is de grootste gemene deler, ggd, van de getallen.

Als deze laatste rest gelijk is aan 1, dan zijn de twee getallen relatief priemgetallen.
Voor de bovenstaande bewerkingen is de laatste niet-nulrest, 201, de grootste gemene deler (ggd) van de getallen 53.667 en 25.527.
Door gebruik te maken van het Euclidische algoritme kunnen we bewijzen dat twee getallen relatief priemgetallen zijn, zie onderstaand voorbeeld.

[1] Begin met het delen van het grotere getal door het kleinere:
87 ÷ 41 = 2 en de Rest = 5 => 87 = 41 × 2 + 5
[2] Deel vervolgens het kleinere getal door de rest van de bovenstaande bewerking:
41 ÷ 5 = 8 en de Rest = 1 => 41 = 5 × 8 + 1
[3] Deel de rest van de eerste bewerking door de rest van de tweede bewerking:
5 ÷ 1 = 5 en de Rest = 0 => 5 = 1 × 5 + 0
De laatste niet-nulrest van de bovenstaande bewerkingen is gelijk aan 1.
ggd (87, 41) = 1, dus de getallen zijn relatief priemgetallen.

Opmerking: De deling 'a' ÷ 'b' = 'q' + 'r' komt overeen met de vergelijking: 'a' = 'b' × 'q' + 'r', waarbij 'q' het quotiënt van de deling is.
Als de laatste waarde van 'r' = 0, dan is de laatste waarde van 'b' een deler van de laatste waarde van 'a' aangezien 'a' = 'b' × 'q' + 0.

Als 'r_n' = 0 => volgens de n^de stap: 'r_(n-1)' is een deler van 'r_(n-2)'.
'r_(n-1)' is ook de laatste niet-nulrest.
Volgens de (n-1)^de stap: 'r_(n-1)' is een deler van zowel 'r_(n-1)' (het getal zelf) als 'r_(n-2)', dus het is ook een deler van 'r_(n-3)'.
Volgens de (n-2)^de stap: 'r_(n-1)' is een deler van zowel 'r_(n-2)' als 'r_(n-3)', dus het is ook een deler van 'r_(n-4)'.
Volgens de (n-3)^de stap: 'r_(n-1)' is een deler van zowel 'r_(n-3)' als 'r_(n-4)', dus het is ook een deler van 'r_(n-5)'.
...
Volgens de 3^e stap: 'r_(n-1)' is een deler van zowel 'r₃' als 'r₂', dus het is ook een deler van 'r₁'.
Volgens de 2^e stap: 'r_(n-1)' is een deler van zowel 'r₂' als 'r₁', dus het is ook een deler van 'b'.
Volgens de 1^ste stap: 'r_(n-1)' is een deler van zowel 'r₁' als 'b', dus het is ook een deler van 'a'.

We hebben dus zojuist aangetoond dat de laatste niet-nulrest, r_(n-1), is een deler van zowel 'a' als 'b'.

Zoals we hierboven zagen, deelt de uiteindelijke niet-nulrest zowel 'a' als 'b' zonder rest. Laten we deze deler 't' noemen.
Volgens de 1^ste delingsstap: Als 't' een deler is van zowel 'a' als 'b', dan is het ook een deler van 'r₁'.
Volgens de 2^e delingsstap: Als 't' een deler is van zowel 'b' als 'r₁', dan is het ook een deler van 'r₂'.
En zo verder, tot aan de (n-1)^de stap: Als 't' een deler is van 'r_(n-3)' als 'r_(n-2)', dan is het ook een deler van 'r_(n-1)'. Maar zoals we hierboven hebben berekend, is deze deler de laatste niet-nulrest, die in ons geval 'r_(n-1)' is.
Dus 't' kan niet groter zijn dan 'r_(n-1)' aangezien het een deler ervan moet zijn.

Het Euclidische algoritme kan ook worden gebruikt om de grootste gemene deler te vinden van meerdere getallen, meer dan twee, zoals 'a', 'b' en 'c'.
Bereken eerst de ggd ('a', 'b') = 'd' en bereken daarna de ggd ('c', 'd').

Voor zeer grote getallen wordt het onpraktisch om het kleinste gemene veelvoud (kgv) te berekenen, omdat het ontbinden in priemfactoren van die getallen te lang duurt.
Met behulp van het Euclidische algoritme wordt niet alleen de grootste gemene deler (ggd) gevonden - zoals hierboven te zien is - maar wordt ook het kleinste gemene veelvoud (kgv) berekend volgens de formule:
kgv ('a', 'b') = ^{('a' × 'b')} / _{ggd ('a', 'b')}
Deze methode kan worden gebruikt als er niet meer dan twee getallen zijn.