Lemma von Euklid

Das Lemma v​on Euklid i​st ein grundlegendes Lemma i​n der klassischen Arithmetik bzw. d​er elementaren Zahlentheorie. Seine Aussage w​ird gewöhnlich z​um Beweis d​es Fundamentalsatz d​er Arithmetik benutzt, genauer z​ur Eindeutigkeit d​er Primfaktorzerlegung. Es taucht s​chon in Euklids Elementen a​uf (Buch VII, Proposition 30).[1]

Das Lemma für natürliche Zahlen

Die zeitgenössische Übersetzung d​er klassischen Formulierung für natürliche o​der ganze Zahlen lautet:

Teilt eine Primzahl ${\displaystyle p}$ ein Produkt ${\displaystyle ab}$, so auch einen (oder beide) der Faktoren.

Äquivalent d​azu ist folgende Verallgemeinerung:

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

Denn falls ${\displaystyle n}$ eine Primzahl ist, erhält man wieder die obere Fassung; ist ${\displaystyle n}$ zusammengesetzt, so gilt es für jeden seiner Primfaktoren und damit für ${\displaystyle n}$ 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 ${\displaystyle \mathbb {N} }$.

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

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

${\displaystyle p(sb)+(ab)t=b}$.

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

${\displaystyle p(sb+ct)=b}$.

Also ist ${\displaystyle p}$ Faktor eines Produktes, das ${\displaystyle b}$ ergibt. Somit teilt es ${\displaystyle b}$, was zu zeigen war.

Anwendungen und Verallgemeinerung

Das Lemma v​on Euklid k​ommt indirekt i​n nahezu j​eder Argumentation mittels Teilbarkeit vor, insbesondere b​ei Primfaktorzerlegungen u​nd dem euklidischen Algorithmus. Bei praktischen Rechenaufgaben spielt d​as Lemma selbst n​ur eine untergeordnete Rolle.

Das Lemma gilt auch für (kommutative) Hauptidealringe: Sei ${\displaystyle H}$ ein Hauptidealring, ${\displaystyle a,b,p\in H}$ und ${\displaystyle p}$ irreduzibel in ${\displaystyle H}$, dann gilt ${\displaystyle p\mid ab\Rightarrow p\mid a\lor p\mid b}$.[2] Hierzu zeigt man die vermeintlich stärkere Aussage, dass das von einem irreduziblen Element ${\displaystyle p}$ erzeugte Hauptideal ${\displaystyle \langle p\rangle }$ bereits ein maximales Ideal ist. In einem Hauptidealbereich fallen die Begriffe "Primideal" und "maximales Ideal" also zusammen.

Ist nämlich ${\displaystyle M\subseteq H}$ ein Ideal mit ${\displaystyle \langle p\rangle \subseteq M}$, so gibt es ein ${\displaystyle m\in H}$ mit ${\displaystyle M=\langle m\rangle }$. Aus ${\displaystyle p\in M=\langle m\rangle }$ folgt also ${\displaystyle p=mc}$ für ein geeignetes ${\displaystyle c\in H}$. Da ${\displaystyle p}$ irreduzibel ist, ist ${\displaystyle m}$ ein Einheit oder ${\displaystyle c}$ eine Einheit von ${\displaystyle H}$. Also folgt ${\displaystyle M=\langle m\rangle =H}$ oder ${\displaystyle m}$ und ${\displaystyle p}$ sind assoziiert und erzeugen dasselbe Hauptideal. Insgesamt erhält man also ${\displaystyle M=H}$ oder ${\displaystyle M=\langle p\rangle }$, was nach Definition bedeutet, dass ${\displaystyle \langle p\rangle }$ maximal ist.

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.