Lemma von Euklid
Das Lemma von Euklid ist ein grundlegendes Lemma in der klassischen Arithmetik bzw. der elementaren Zahlentheorie. Seine Aussage wird gewöhnlich zum Beweis des Fundamentalsatzes der Arithmetik benutzt, genauer zur Eindeutigkeit der Primfaktorzerlegung. Es taucht schon in Euklids Elementen auf (Buch VII, Proposition 30).[1]
Das Lemma für natürliche Zahlen
Die zeitgenössische Übersetzung der klassischen Formulierung für natürliche oder ganze Zahlen lautet:
Äquivalent dazu ist folgende Verallgemeinerung:
- Teilt
das Produkt
und ist teilerfremd zu einem der Faktoren, so teilt es den anderen.
Denn falls eine Primzahl ist, erhält man wieder die obere Fassung; ist
zusammengesetzt, so gilt es für jeden seiner Primfaktoren und damit für
selbst.
Beweis
Der Beweis des Lemmas kann klassisch als direkter Beweis geführt werden, er nutzt das Lemma von Bézout und argumentiert damit teilweise außerhalb der natürlichen Zahlen, die Aussage gilt aber offensichtlich auch eingeschränkt auf .
Seien beliebig. Angenommen, eine Primzahl
teilt das Produkt
, aber nicht den Faktor
. Dann ist zu zeigen, dass
ein Teiler von
ist.
Aus der Annahme folgt insbesondere, dass und
teilerfremd sind. Mit Bézout existieren dann zwei ganze Zahlen
und
, sodass
gilt. Diese Gleichung mit
multipliziert und etwas umsortiert liefert
.
Laut Annahme existiert ein mit
, damit lässt sich
auf der linken Seite der Gleichung ausklammern:
.
Also ist Faktor eines Produktes, das
ergibt. Somit teilt es
, was zu zeigen war.
Anwendungen und Verallgemeinerung
Das Lemma von Euklid kommt indirekt in nahezu jeder Argumentation mittels Teilbarkeit vor, insbesondere bei Primfaktorzerlegungen und dem euklidischen Algorithmus. Bei praktischen Rechenaufgaben spielt das Lemma selbst nur eine untergeordnete Rolle.
Das Lemma gilt auch für (kommutative) Hauptidealringe: Sei ein Hauptidealring,
und
irreduzibel in
, dann gilt
.[2]Hierzu zeigt man die vermeintlich stärkere Aussage, dass das von einem irreduziblen Element
erzeugte Hauptideal
bereits ein maximales Ideal ist. In einem Hauptidealbereich fallen die Begriffe „Primideal“ und „maximales Ideal“ also zusammen.
Ist nämlich ein Ideal mit
, so gibt es ein
mit
. Aus
folgt also
für ein geeignetes
. Da
irreduzibel ist, ist
ein Einheit oder
eine Einheit von
. Also folgt
oder
und
sind assoziiert und erzeugen dasselbe Hauptideal. Insgesamt erhält man also
oder
, was nach Definition bedeutet, dass
maximal ist.