Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I/Vorlesung 21

Aus Wikiversity
Wechseln zu: Navigation, Suche
„Ein guter Schüler lernt auch bei einem schlechten Lehrer ...“



Kleinstes gemeinsames Vielfaches und größter gemeinsamer Teiler

Zu einer ganzen Zahl besteht aus allen Vielfachen von . Zu zwei Zahlen besteht somit der Durchschnitt aus allen Zahlen, die sowohl von als auch von Vielfache sind, also aus allen gemeinsamen Vielfachen von und . In der Tat gilt die folgende Aussage.



Lemma  

Es seien ganze Zahlen.

Dann ist

wobei das kleinste gemeinsame Vielfache der ist.

Beweis  

Nach Aufgabe 21.24 ist der Durchschnitt der Untergruppen wieder eine Untergruppe von . Nach Satz 20.4 gibt es ein eindeutig bestimmtes mit

Wegen

für alle ist ein Vielfaches von jedem , also ein gemeinsames Vielfaches der . Für jedes gemeinsame Vielfache dieser Elemente gilt

Die Zahl besitzt also die Eigenschaft, dass jedes gemeinsame Vielfache der Elemente ein Vielfaches von ist. Daher ist das kleinste gemeinsame Vielfache.


Für ganze Zahlen setzen wird den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache stets positiv an, um Eindeutigkeit zu erzielen. Grundsätzlich hat jeweils das Negative dazu die gleichen Eigenschaften.



Lemma  

Für natürliche Zahlen gelten folgende Aussagen.

  1. Für teilerfremde ist .
  2. Es gibt mit und , wobei teilerfremd sind.
  3. Es ist .
  4. Es ist .

Beweis  

  1. Zunächst ist natürlich das Produkt ein gemeinsames Vielfaches von und . Sei also irgendein gemeinsames Vielfaches, also und . Nach Satz 20.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 wäre.
  3. Die rechte Seite ist offenbar ein gemeinsames Vielfaches von und . Sei ein Vielfaches der linken Seite, also ein gemeinsames Vielfaches von und . Dann kann man schreiben und . Damit ist und somit ist (bei ; ist erst recht ein Vielfaches der rechten Seite) ein gemeinsames Vielfaches von und . Also ist ein Vielfaches der rechten Seite.
  4. Wir schreiben unter Verwendung der ersten Teile


Der Teil (4) der vorstehenden Aussage erlaubt es, das kleinste gemeinsame Vielfache zu zwei Zahlen algorithmisch dadurch zu bestimmen, dass man ihren größten gemeinsamen Teiler mit Hilfe des euklidischen Algorithmus bestimmt und das Produkt durch diesen teilt.



Der Hauptsatz der elementaren Zahlentheorie

Wir möchten nun zur Primfaktorzerlegung, deren Existenz wir bereits in Satz 12.9 gezeigt haben, beweisen, dass sie eindeutig ist. Natürlich kann man

schreiben, mit eindeutig ist also eindeutig bis auf die Reihenfolge gemeint. Um dies zu zeigen brauchen wir zunächst das sogenannte Lemma von Euklid, das eine wichtige Eigenschaft einer Primzahl beschreibt.


Satz  

Es sei eine Primzahl und teile ein Produkt von natürlichen Zahlen .

Dann teilt einen der Faktoren.

Beweis  

Wir setzen voraus, dass kein Vielfaches von ist (andernfalls sind wir fertig). Dann müssen wir zeigen, dass ein Vielfaches von ist. Unter der gegebenen Voraussetzung sind und teilerfremd. Nach dem Lemma von Bezout gibt es ganze Zahlen mit

Da ein Vielfaches von ist, gibt es ein mit

Daher ist

Also ist ein Vielfaches von .


Aus dem Lemma von Euklid folgt sofort die etwas stärkere Aussage: Wenn eine Primzahl ein beliebiges Produkt teilt, dann teilt mindestens einen Faktor. Man wendet das Lemma einfach auf an (formal ist das eine Induktion über die Anzahl der Faktoren). Dies wird im Beweis des folgenden Hauptsatzes der elementaren Zahlentheorie verwendet.


Satz  

Jede natürliche Zahl , , besitzt eine eindeutige Zerlegung in Primfaktoren.

D.h. es gibt eine Darstellung

mit Primzahlen , und dabei sind die Primfaktoren bis auf ihre Reihenfolge eindeutig bestimmt.

Beweis  

Die Existenz der Primfaktorzerlegung wurde bereits in Satz 12.9 gezeigt. Die Eindeutigkeit wird durch Induktion über gezeigt. Für liegt eine Primzahl vor. Sei nun und seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir

Wir müssen zeigen, dass nach Umordnung die Primfaktorzerlegungen übereinstimmen. Die Gleichheit bedeutet insbesondere, dass die Primzahl das Produkt rechts teilt. Nach Satz 20.7 muss dann einen der Faktoren rechts teilen. Nach Umordnung können wir annehmen, dass von geteilt wird. Da selbst eine Primzahl ist, folgt, dass sein muss. Daraus ergibt sich durch Kürzen, dass

ist. Nennen wir diese Zahl . Da ist, können wir die Induktionsvoraussetzung auf anwenden und erhalten, dass links und rechts die gleichen Primzahlen stehen. 

In der kanonischen Primfaktorzerlegung schreibt man die beteiligten Primzahlen in aufsteigender Reihenfolge mit ihrem jeweiligen Exponenten, also beispielsweise

Damit ist insbesondere zu jeder ganzen Zahl und jeder Primzahl eindeutig bestimmt, ob in der Primfaktorzerlegung überhaupt vorkommt und wenn ja mit welchem Exponenten.


Definition  

Zu einer ganzen Zahl und einer Primzahl nennt man den Exponenten, mit dem in der Primfaktorzerlegung von vorkommt, den -Exponenten von . Er wird mit bezeichnet.

Statt Exponent spricht man auch von der Vielfachheit oder der Ordnung von in . Wenn in der Primfaktorzerlegung nicht vorkommt, so ist

Die Primfaktorzerlegung einer Zahl kann man damit abstrakt und kompakt als

schreiben. Da in jeder Primfaktorzerlegung nur endlich viele Primzahlen wirklich vorkommen, ist dies ein endliches Produkt.

Zu ist die Primfaktorzerlegung gleich

und somit gilt

und

für alle weiteren Primzahlen .



Lemma

Es sei eine Primzahl und

der zugehörige -Exponent. Dann gelten folgende Aussagen.

  1. Die Zahl ist die größte Potenz von , die teilt.
  2. Es ist
  3. Es ist

    (es sei vorausgesetzt).

Beweis

Siehe Aufgabe 21.15.




Korollar  

Es seien und positive natürliche Zahlen. Dann wird von genau dann geteilt,

wenn für jede Primzahl die Beziehung

gilt.

Beweis  

. Aus der Beziehung folgt in Verbindung mit der eindeutigen Primfaktorzerlegung, dass die Primfaktoren von mit mindestens ihrer Vielfachheit auch in vorkommen müssen.
. Wenn die Exponentenbedingung erfüllt ist, so ist eine natürliche Zahl mit .

Aus diesem Kriterium ergibt sich, dass man zu einer gegebenen Zahl, deren Primfaktorzerlegung vorliegt, einfach alle Teiler angeben kann. Bei

sind die (positiven) Teiler genau die Zahlen

Davon gibt es Stück.



Korollar  

Es seien und positive natürliche Zahlen mit den Primfaktorzerlegungen und .

Dann ist

und

Beweis  

Dies folgt direkt aus Korollar 20.7.


Für die beiden Zahlen und ist beispielsweise der größte gemeinsame Teiler gleich und das kleinste gemeinsame Vielfache gleich .


<< | Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)