Euklidischer Algorithmus/Z/Einführung/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Es seien ganze Zahlen, . Dann kann man die Division mit Rest durchführen und erhält mit . Danach kann man (bei ) die Division mit Rest von durch durchführen, d.h. nimmt die Rolle von und die Rolle von ein und erhält einen neuen Rest. Dies kann man fortsetzen, und da dabei die Reste immer kleiner werden bricht das Verfahren irgendwann ab.



Definition  

Seien zwei ganze Zahlen (mit ) gegeben. Dann nennt man die durch die Anfangsbedingungen und und die mittels der Division mit Rest

rekursiv bestimmte Folge die Folge der euklidischen Reste.



Satz  

Seien ganze Zahlen und gegeben.

Dann besitzt die Folge , , der euklidischen Reste folgende Eigenschaften.

  1. Es ist oder .
  2. Es gibt ein (minimales) mit .
  3. Es ist

    für alle

  4. Sei der erste Index derart, dass ist. Dann ist

Beweis  

  1. Dies folgt unmittelbar aus der Definition der Division mit Rest.
  2. Solange ist, wird die Folge der natürlichen Zahlen immer kleiner, so dass irgendwann der Fall eintreten muss.
  3. Wenn ein gemeinsamer Teiler von und von ist, so zeigt die Beziehung

    dass auch ein Teiler von und damit ein gemeinsamer Teiler von und von ist. Die Umkehrung folgt genauso.

  4. Dies folgt aus (3) mit der Gleichungskette


Beispiel

Aufgabe

Bestimme in mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von und .


Lösung

Der Euklidische Algorithmus liefert:

Die Zahlen und sind also teilerfremd.


Bei kleinen Zahlen sieht man häufig relativ schnell direkt, was ihr größter gemeinsamer Teiler ist, da man die Primfaktorzerlegung kennt bzw. mögliche gemeinsame Teiler schnell übersehen kann. Bei zwei größeren Zahlen müssten aber viel zu viele Probedivisionen durchgeführt werden! Der euklidische Algorithmus ist also zur Bestimmung des größten gemeinsamen Teilers ein sehr effektives Verfahren!