Zum Inhalt springen

Kurs:Einführung in die Algebra (Osnabrück 2009)/Vorlesung 4

Aus Wikiversity



Das Lemma von Bezout



Jede Menge von ganzen Zahlen

besitzt einen größten gemeinsamen Teiler , und dieser lässt sich als Linearkombination der darstellen, d.h. es gibt ganze Zahlen mit

Insbesondere gibt es zu teilerfremden ganzen Zahlen eine Darstellung der .

Dies folgt direkt aus Lemma 3.9 und Satz 3.2.


Man beachte, dass ein größter gemeinsamer Teiler, der nach dem Lemma von Bézout existiert, nicht eindeutig bestimmt ist. Denn ebenso ist mit auch das Negative ein größter gemeinsamer Teiler. Häufig wählt man den Vertreter , um Eindeutigkeit zu erreichen, und spricht dann von dem größten gemeinsamer Teiler der . Diese Zahl wird dann mit

bezeichnet. Wir besprechen nun, wie man algorithmisch zu vorgegebenen ganzen Zahlen den finden kann.



Der Euklidische Algorithmus

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.



Es 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.



Es seien ganze Zahlen und gegeben.

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

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

    für alle

  4. Sei der erste Index derart, dass ist. Dann ist
  1. Dies folgt unmittelbar aus der Definition der Division mit Rest.
  2. Solange ist, wird die Folge der natürlichen Zahlen immer kleiner, sodass 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!



Darstellung des größten gemeinsamen Teilers

Mit dem euklidischen Algorithmus kann man auch durch Zurückrechnen eine Darstellung des größten gemeinsamen Teilers als Linearkombination der beiden vorgegebenen Zahlen erhalten. Dazu seien

die Gleichungen im euklidischen Algorithmus und . Aus der letzten Gleichung

erhält man die Darstellung

von als Linearkombination mit und . Mit der vorhergehenden Zeile

bzw.

kann man in dieser Darstellung ersetzen und erhält eine Darstellung von als Linearkombination von und . So fortfahrend erhält man schließlich eine Darstellung von

als Linearkombination von und .


Wir wollen für und eine Darstellung des größten gemeinsamen Teilers finden. Wir führen dazu den euklidischen Algorithmus durch.

D.h. ist der größte gemeinsame Teiler von und . Rückwärts gelesen erhält man daraus die Darstellung




Gemeinsame Vielfache

Nachdem wir schon die gemeinsamen Teiler von ganzen Zahlen behandelt haben, wenden wir uns einem verwandten Begriff zu, der ebenfalls aus der Schule bekannt ist, nämlich dem des kleinsten gemeinsamen Vielfachen von ganzen Zahlen. In der Schule wird dabei „kleinste“ in Bezug auf die -Ordnung verstanden. Wir benutzen einen äquivalenten Begriff, der sich besser auf eine weit allgemeinere Situation übertragen lässt.


Zu einer Menge von ganzen Zahlen

heißt eine ganze Zahl ein gemeinsames Vielfaches, wenn ein Vielfaches von jedem ist, also von jedem geteilt wird. Die Zahl heißt ein kleinstes gemeinsames Vielfaches der , wenn ein gemeinsames Vielfaches ist und wenn jedes andere gemeinsame Vielfache ein Vielfaches von ist.

Wir werden gleich sehen, dass es stets ein kleinstes gemeinsames Vielfaches gibt, und dass dieses, wenn man es wählt, auch eindeutig bestimmt ist. Man spricht dann einfach von dem kleinsten gemeinsamen Vielfachen, geschrieben .



Zu einer Menge von ganzen Zahlen

existiert genau ein kleinstes gemeinsames Vielfaches ,

und zwar ist der eindeutig bestimmte Erzeuger der Untergruppe

Es ist klar, dass eine ganze Zahl ein gemeinsames Vielfaches der ist genau dann, wenn

gilt. Nach Satz 3.2 gibt es ein eindeutig bestimmtes mit

Nach der Vorüberlegung ist daher ein gemeinsames Vielfaches und für jedes weitere gemeinsame Vielfache gilt

Dies bedeutet, dass ein Vielfaches von ist.



Für natürliche Zahlen gelten folgende Aussagen.

  1. Für teilerfremde ist
  2. Es gibt mit

    wobei teilerfremd sind.

  3. Es ist
  4. Es ist
  1. Zunächst ist natürlich das Produkt ein gemeinsames Vielfaches von und . Es sei also irgendein gemeinsames Vielfaches, also und . Nach Satz 4.1 gibt es im teilerfremden Fall Zahlen mit . Daher ist

    ein Vielfaches von .

  2. Die Existenz von und ist klar. Hätten und einen gemeinsamen Teiler , so ergäbe sich sofort der Widerspruch, dass ein größerer gemeinsamer Teiler von und wäre.
  3. Die rechte Seite ist offenbar ein gemeinsames Vielfaches von und . Es sei ein Vielfaches der linken Seite, also ein gemeinsames Vielfaches von und . Dann kann man und schreiben. Damit ist und somit ist (bei ; bei ist die Behauptung direkt klar) ein gemeinsames Vielfaches von und . Also ist ein Vielfaches der rechten Seite.
  4. Wir schreiben unter Verwendung der ersten Teile




Fußnoten
  1. Für . Da auch negativ sein könnte ist dies bei als zu lesen.



<< | Kurs:Einführung in die Algebra (Osnabrück 2009) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)