Inhalts-Button  

Euklidischer Algorithmus

Der Euklidische Algorithmus ist ein Verfahren, den ggT zu bestimmen, ohne auf die Primfaktorzerlegung zurückzugreifen.
Zunächst müssen noch zwei Sätze bewiesen werden, um den Beweis zum Euklidischen Algorithmus vorzubereiten.

  

Primfaktorzerlegung /
Euklidscher Algorithmus
Euklidscher Algorithmus
(funktioniert nur bei installiertem OpenOffice)
 
   
Satz 4: "Division mit Rest"

Seien a, b .
Wenn b | a,
dann gibt es genau ein Paar q, r , so dass
a = q · b + r mit 0 ≤ r < b.

   
Zusammenfassungs-Button   Beweis    
 
   
Beispiel: a = 29, b = 7
  29 = 4 · 7 + 1
  q = 4, r = 1
   
 
   
Satz 5: "Teiler-Schnittmenge"

Seien a, b .
Wenn a = q · b + r mit 0 ≤ r < b,
dann gilt: T(a) T(b) = T(b) T(r).
   
Zusammenfassungs-Button   Beweis    
 
   
Beispiel: a = 16, b = 6, also a = 2 · b + 4
  T(16) T(6) = {1, 2}
  T(6) T(4) = {1, 2}
  Also gilt: T(16) T(6) = T(6) T(4)
   
 
    Es folgt aus diesem Satz:
Da T(a) T(b) = T(b) T(r), muss für a > b gelten:
ggT(a,b) = ggT (b,r) weil die Teilermengen gleich sind und somit der ggT(a,b) auch der ggT(b,r) ist.
   
 
   
Satz 6: "Der Euklidische Algorithmus"

Wenn a, b mit a > b sind,
dann gibt es qi, ri und ein n , so dass gilt:


      

Man erhält dann: T(a) T(b) = T(rn+1) und ggT(a,b) = rn+1.

   
 
Zusammenfassungs-Button   Beweis    
 
   
Beispiel: a = 164, b = 44
 
  ggT(164,44) = 4
   
 
Button Aufgabe  

Übung:

Ermitteln Sie mit Hilfe des Euklidischen Algorithmus
den ggT von 781 und 638.