Euklidischer Algorithmus

 

 

Der Euklidische Algorithmus dient zur Bestimmung des ggT zweier (großer) Zahlen. Der Algorithmus läuft wie folgt ab:

  1. Im ersten Schritt dividieren wir die größere der beiden Zahlen durch die kleinere.
  2. Ergibt sich der Rest 0, so ist der Divisor der gesuchte ggT.
  3. Ist der Rest nicht 0, so wird der ehemalige Divisor zum Dividenden und der berechnete Rest zum Divisor eines weiteren Quotienten.
  4. Führe das Verfahren bei Schritt 2. weiter.

Beispiel: ggT(48 548 ; 4293) = 53, denn:

 

     Dividend   Divisor       Rest
 48 548 =  4 293 ·  11 +  1 325
4 293 = 1 325 · 3  +  318
1 325 =  318 · 4  + 53 
 318 = 53  · 6     

 

Kennen wir den ggT zweier Zahlen a und b (mit a < b), so erhalten wir das kgV nach folgender Rechnung: kgV = b · (a : ggT),
im Beispiel:

kgV(48 548 ; 4 293)  = 48 548 · (4 293 : 53) = 48 548 · 81 = 3 932 388.

 

Zugriffe: 1193