Algoritme van Euclides
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: Als ax + by = c, een diofantische oplossing heeft, dan en slechts dan, ggd(a,b) een deler van c.
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
.....25..34
--------------
34....0...1
25....1...0
--------------
9....-1...1
7.....3..-2
2....-4...3
1....15.-11 => (15)25 + (-11)34 = 1
--------------
-3..-45..33 => (-45)25 + (33)34) = -3
Deze tabel geeft de lineaire combinaties aan.
rij 1: 34 = (0)25 + (1)34 rij 2: 25 = (1)25 + (0)34 rij 3: 34 - 1 * 25 = 9, 0 - 1 = -1, en 1 - 0 = 1 rij 4: 25 - 2 * 9 = 7 ... rij 7: rij 5 -3 * rij 6
Als (-45)25 + (33)34) = -3 dan geldt: (-45)25 - (-33)34) = -3 en dat geeft ons één oplossing: (x,y)=(-45,-33)
Stap 3: Vind alle oplossingen.
We hebben nu (-45)25 - (-33)34) = -3.
Maar ook (-45 + 34)25 - (-33 + 25)34 = -3.
Algemeen: (-45 + 34k)25 - (-33 + 25k)34 = -3. (x,y)=(34k-45,25k-34) voor alle k uit Z.
[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))))