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 Fundamentalsatz der Arithmetik benutzt, genauer zur Eindeutigkeit der Primfaktorzerlegung. Es taucht schon in Euklids Elementen auf (Buch VII, Proposition 30).

Das Lemma für natürliche Zahlen 
Die zeitgenössische Übersetzung der klassischen Formulierung für natürliche oder ganze Zahlen lautet:
 Teilt eine Primzahl  ein Produkt , so auch einen (oder beide) der Faktoren.
Ä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 .
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.

Einzelnachweise 

Euklid, Lemma von