Die Aussage der elementaren Zahlentheorie, dass wenn eine Primzahl p das Produkt ab zweier ganzer Zahlen a und b teilt, dann p a oder p b teilt.

Prinzip

Primzahlen sind hinsichtlich der Teilbarkeit unzerlegbar: ein Primteiler eines Produkts muss bereits einen der Faktoren teilen; dies ordnet viele Argumente zu Teilbarkeit und Faktorisierung.

Demonstration

Beispiel: p = 3 und 3 teilt 9·4 = 36; da 3 9 teilt, gilt das Lemma. Strukturell: Wenn p ab teilt und p a nicht teilt, so ist ggT(a,p)=1; mit ax+py=1 für geeignete ganze x,y und Multiplikation mit b folgt, dass p b teilt.

Fehlanwendung

Das Ergebnis auf eine zusammengesetzte Zahl c anwenden: für ein zusammengesetztes c, das ab teilt, ist es im Allgemeinen falsch, dass c a oder c b teilt; das Lemma in Ringen ohne geeignete Definition von Prim oder ggT anwenden, ohne Voraussetzungen zu prüfen.

Konsequenz

Ist ein entscheidender Schritt beim Beweis der Eindeutigkeit der Primfaktorzerlegung in Z und erlaubt, von Produktteilbarkeit auf Faktorenteilbarkeit zu schließen, was viele Induktionsargumente stützt.

Umkehrung

Die triviale Umkehrung lautet: wenn p a teilt, dann teilt p ab; wichtig ist jedoch der Gegensatz, dass das Ersetzen von 'prim' durch 'zusammengesetzt' die Aussage zerstört und Gegenbeispiele liefert.

Abgrenzung

Gilt für primäre Elemente in Integritätsbereichen mit einer passenden Primalitätsdefinition; am einfachsten formuliert für Primzahlen in Z. In Ringen, in denen Irreduzible nicht prim sind, gilt es nicht automatisch.

Semantische Spannung

Spannung zwischen 'prim' und 'irreduzibel': In manchen Ringen erfüllen irreduzible Elemente nicht das Lemma, wodurch die Unterscheidung zwischen primen Elementen (die Faktorenteilbarkeit erzwingen) und bloßen Irreduziblen entsteht.

Synthese

Euklids Lemma fasst die wesentliche Teilbarkeitseigenschaft primärer Elemente zusammen: teilt ein Primzahl ein Produkt, so lokalisiert sich die Teilbarkeit auf einen Faktor; dies ist zentral für die Eindeutigkeit der Faktorisierung und für die Überführung von Produktinformation auf Faktoren.