Algoritme van Euclides
Van Wikipedia
Het algoritme van Euklides, genoemd naar de Griekse wiskundige Euklides, is een algoritme (rekenwijze) voor het bepalen van de grootste gemene deler (hierna: ggd) van twee positieve gehele getallen. Er is ook een uitgebreidere variant op dit algoritme.
Inhoud |
[bewerk] Het algoritme
- Noem het grootste van de beide getallen A, het andere B.
- Trek B net zo vaak van A af totdat er 0 over blijft of een getal kleiner dan B.
- Wanneer er 0 over blijft zijn we klaar, en is B de ggd.
- Zo niet, herhaal dan het algoritme met B en wat er van A over is.
[bewerk] Voorbeeld
Als een voorbeeld bepalen we met het algoritme van Euklides de ggd van 900 en 1140:
- A is 1140, B is 900. We kunnen 900 eenmaal van 1140 aftrekken, we krijgen dan 240.
- We herhalen het algoritme met A=900 en B=240. 240 kan driemaal van 900 worden afgetrokken, dan blijft 180 over.
- We herhalen het algoritme met A=240 en B=180. 180 kan eenmaal van 240 worden afgetrokken. Dit levert 60.
- We herhalen het algoritme met A=180 en B=60. 60 kan 3 maal van 180 afgetrokken worden, en 0 blijft dan over.
- Daarmee zijn we aan het einde gekomen, en hebben bepaald dat 60 de grootste gemene deler van 900 en 1140 is, oftewel ggd(900,1140)=60.
[bewerk] Uitbreiding
Met dit algoritme is het mogelijk diofantische vergelijkingen op te lossen van de vorm: ax + by + ... = c.
Stelling: ax + by = c heeft een diofantische oplossing dan en slechts dan als ggd(a,b) een deler van c is.
Bewijs [=>] triviaal. [<=] Er is zeker een oplossing van de diofantische vergelijking ax + by = ggd(a,b) (probeer maar m.b.v. het Algoritme van Euklides). Omdat nu gegeven is dat c een veelvoud van ggd(a,b) is, kunnen we de vergelijking links en rechts vermenigvuldigen met c/ggd(a,b). Q.E.D.
Oplossingsmethode a.d.v. een voorbeeld: Opgave: 50x - 68y = -6
Oplossing
Stap 1: Om alle oplossingen te vinden, moeten we eerst de vergelijking links en rechts delen door ggd(50,68)= 2. 25x - 34y = -3
Stap 2: Los op: 25x + 34y = 1
| x (* 25) | y (* 34) | uitkomst | opmerking |
|---|---|---|---|
| 0 | 1 | 34 | Dit betekent: (0 * 25 + 1 * 34) = 34 |
| 1 | 0 | 25 | |
| -1 | 1 | 9 | 9 = 34 - 25 = (0 * 25 + 1 * 34) - (1 * 25 + 0 * 34) = (-1 * 25 + 1 * 34) |
| 3 | -2 | 7 | 7 = 25 - 2 * 9 = (1 * 25 + 0 * 34) - 2 * (-1 * 25 + 1 * 34) = (3 * 25 + -2 * 34) |
| -4 | 3 | 2 | |
| 15 | -11 | 1 |
Nu we de x- en y-waarden bij uitkomst 1 hebben gevonden, kunnen we een oplossing vinden voor uitkomst -3, door deze waarden simpelweg met -3 te vermenigvuldigen. Dit levert op:
(-45) * 25 + (33) * 34 = -3 => (-45) * 25 - (-33) * 34 = -3
Dit is dus één oplossing: (x, y) = (-45, -33).
Stap 3: Vind alle oplossingen.
Naast deze oplossing, is de volgende er ook één.
(-45 + 34) * 25 - (-33 + 25) * 34 = -3.
In het algemeen geldt, voor alle k uit Z:
(-45 + 34 * k) * 25 - (-33 + 25 * k) * 34 = -3 => (x, y) = (34 * k - 45, 25 * k - 33)
[bewerk] Implementatie
C/C++/Java
Een recursieve vorm in C, C++ en Java ziet er alsvolgt uit:
int ggd(int a, int b){
if(b==0){
return a;
}else{
return ggd(b,a%b);
}
}
Een iteratieve versie:
int ggd(int a, int b){
int rest;
while(b != 0){
rest=a%b;
a=b;
b=rest;
}
return a;
}
Scheme
Een recursieve implementatie in scheme ziet er alsvolgt uit:
(define (ggd a b)
(if (= b 0)
a
(ggd b (remainder a b))))
