zum Directory-modus

Euklidischer Algorithmus

Der Euklidische Algorithmus

Theorem
Seien a , b mit b > 0 . Dann existieren eindeutige Zahlen q , r mit 0 r < b , so dass gilt
a = q b + r .
Die ganze Zahl q heißt der Quotient und r der Rest.

Z.B. für die Zahlen a = 19665 , b = 79 gilt

19665 = 248 79 + 73 ,

wobei q = 248 und r = 73 ist.

Theorem
Seien a , b , q , r mit a = q b + r . Dann ist
( m , n ) = ( n , r ) .

Dieser Satz ist die Grundlage des Euklidischen Algorithmus.

Euklidischer Algorithmus

Der Euklidische Algorithmus ist einer der ältesten und berühmtesten Algorithmen überhaupt. Er dient zur Bestimmung des größten gemeinsamen Teilers zweier positiver ganzer Zahlen a und b mit a > b .

Der Algorithmus funktioniert wie folgt:

  1. Man dividiert a durch b und erhält einen Rest r
  2. Ist r = 0 , ist ( a , b ) = b .
  3. Ist r 0 , wird a der Wert von b zugewiesen und b der Wert von r . Man wiederhole dann den Zyklus ab Schritt 1 bis der Rest 0 ist. Der entsprechende Wert von b ist dann der gesuchte ( a , b ) .

Man setzt r -1 = a , r 0 = b . Dann ist

Division von r -1 durch r 0 : r -1 = q 1 r 0 + r 1 mit 0 < r 1 < r 0 Division von r 0 durch r 1 : r 0 = q 2 r 1 + r 2 mit 0 < r 2 < r 1 Division von r 1 durch r 2 : r 1 = q 3 r 2 + r 3 mit 0 < r 3 < r 2 Division von r i -2 durch r i -1 : r i -2 = q i r i -1 + r i mit 0 < r i < r i -1 Division von r n -3 durch r n -2 : r n -3 = q n -1 r n -2 + r n -1 mit 0 < r n -1 < r n -2 Division von r n -2 durch r n -1 : r n -2 = q n r n -1 + r n ,

wobei r n = 0 . Die Reste bilden eine Reihe von abnehmenden natürlichen Zahlen

r 1 > r 2 > r 3 > r n -1 > r n = 0

und so erhält man irgendwann einen Nullwert r n = 0 . Der gesuchte ( a , b ) ist r n -1 .

Der Algorithmus funktioniert, da wegen des obigen Satzes

( a , b ) = ( b , r 1 ) = ( r 1 , r 2 ) = ( r 2 , r 3 ) = = ( r n -2 , r n -1 ) = ( r n -1 , 0 ) = r n -1 .

ist.

Beispiel

Bestimmung von ( 2782 , 2249 ) :

Division von 2782 durch 2249 : 2782 = 1 2249 + 533 Division von 2249 durch 533 : 2249 = 4 533 + 117 Division von 533 durch 117 : 533 = 4 117 + 65 Division von 117 durch 65 : 117 = 1 65 + 52 Division von 65 durch 52 : 65 = 1 52 + 13 Division von 52 durch 13 : 52 = 4 13 + 0

Der letzte Rest, der nicht 0 ist, ist 13 . Also ist ( 2782 , 2249 ) = 13 . Es gilt

( 2782 , 2249 ) = ( 2249 , 533 ) = ( 533 , 117 ) = ( 117 , 65 ) = ( 65 , 52 ) = ( 52 , 13 ) = ( 13 , 0 ) = 13 .

Kettenbrüche

Schreibt man die Zeilen des obigen Beispiels in der Form

2782 2249 = 1 + 533 2249 2249 533 = 4 + 117 533 533 117 = 4 + 65 117 117 65 = 1 + 52 65 65 52 = 1 + 13 52 52 13 = 4 ,

führt das zu einer ungewohnten Art der Darstellung eines Bruches:

2782 2249 = 1 + 533 2249 = 1 + 1 2249 533 = 1 + 1 4 + 117 533 = 1 + 1 4 + 1 533 117 = 1 + 1 4 + 1 4 + 65 117 = 1 + 1 4 + 1 4 + 1 117 65 = 1 + 1 4 + 1 4 + 1 1 + 52 65 = 1 + 1 4 + 1 4 + 1 1 + 1 65 52 = 1 + 1 4 + 1 4 + 1 1 + 1 1 + 13 52 = 1 + 1 4 + 1 4 + 1 1 + 1 1 + 1 4 .

Also ist

2782 2249 = 1 + 1 4 + 1 4 + 1 1 + 1 1 + 1 4 = [ 1 , 4 , 4 , 1 , 1 , 4 ] abgekürzt .

Die rechte Seite der Gleichung ist ein sogenannter Kettenbruch, d.h. ein Bruch, dessen Nenner immer ein weiterer Bruch ist. Bei einer rationalen Zahl wie hier bricht die Kettenbruchentwicklung ab.

In Form von den Quotienten q i im Euklidischen Algorithmus ist die Kettenbruchentwicklung des Bruches a / b gegeben durch

a b = q 1 + 1 q 2 + 1 q 3 + = [ q 1 , q 2 , , q n ] q i 0 , q i 1 für 1 < i < n und q n 2 .
<Seite 1 von 1>