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, Postulat 30). ^[1]

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 p ein Produkt ab, so auch einen (oder beide) der Faktoren.

Äquivalent dazu ist folgende Verallgemeinerung:

Teilt $n \in \N$ das Produkt ab und ist teilerfremd zu einem der Faktoren, so teilt es den anderen.

Denn falls n eine Primzahl ist, erhält man wieder die obere Fassung, ist n zusammengesetzt, so gilt es für jeden seiner Primfaktoren und damit für n selbst. UNIQ12b22c6f39cf4f17-math-0000000A-QINU

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 $\N$.

Seien $a,b \in \Z$ beliebig. Angenommen, eine Primzahl p teilt das Produkt ab, aber nicht den Faktor a. Dann ist zu zeigen, dass p ein Teiler von b ist.

Aus der Annahme folgt insbesondere, dass a und p teilerfremd sind, mit Bézout existieren dann zwei ganze Zahlen s und t sodass sp + ta = 1 gilt. Diese Gleichung mit b multipliziert und etwas umsortiert liefert

p(sb) + (ab)t = b.

Laut Annahme existiert ein $c \in \Z$ mit ab = cp, damit lässt sich p auf der linken Seite der Gleichung ausklammern:

p(sb + ct) = b.

Also ist p Faktor eines Produktes, das b ergibt. Somit teilt es b und das war zu zeigen.

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 Hauptidealringe: Sei H ein Hauptidealring, $a,b,p \in H$ und p irreduzibel in H, dann gilt $p \mid ab \Rightarrow p \mid a \or p \mid b$.^[2]

Einzelnachweise

1. ↑ Euklids Elemente, Buch VII, Prop 30 (englisch Übersetzung, mit orig. Beweis)
2. ↑ Jürgen Wolfart: Einführung in die Algebra und Zahlentheorie. Vieweg, Braunschweig/Wiesbaden 1996, ISBN 3-528-07286-5, S. 76.