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

Bearbeiten

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.

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

Bearbeiten

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.

Einzelnachweise

Bearbeiten
  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.