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 1 Het algoritme 2 Voorbeeld 3 Uitbreiding 4 Implementatie

[bewerk] Het algoritme

1. Noem het grootste van de beide getallen A, het andere B.
2. Trek B net zo vaak van A af totdat er 0 over blijft of een getal kleiner dan B.
3. Wanneer er 0 over blijft zijn we klaar, en is B de ggd.
4. 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))))