3. Das Lemma von Euklid, I

Das Lemma von Euklid lautet:

Satz (Lemma von Euklid, Teilbarkeitssatz von Euklid)

Seien a, b ≥ 1 natürliche Zahlen, und sei p eine Primzahl, die das Produkt ab teilt. Dann ist p ein Teiler von a oder ein Teiler von b.

Mit Hilfe der Teilbarkeitsnotation d|n für „d ist ein Teiler von n“ können wir das Lemma so formulieren:

Satz (Lemma von Euklid, II)

Seien a, b ≥ 1 natürliche Zahlen, und sei p eine Primzahl. Dann gilt:

p|ab impliziert p|a oder p|b.

Logisch äquivalent ist:

Satz (Lemma von Euklid, III)

Seien a, b ≥ 1 natürliche Zahlen, und sei p eine Primzahl. Dann gilt:

p|ab und ¬p|a impliziert p|b.

Aus dem Lemma von Euklid ergab sich die Eindeutigkeit der Primfaktorzerlegung ohne große Mühe. Wie lässt sich nun aber das Lemma selbst beweisen? Betrachten wir hierzu den einfachen Fall, dass nicht nur der Teiler, sondern auch die Faktoren prim sind. Wir haben also drei Primzahlen p, q₁, q₂ vorliegen derart, dass p ein Teiler von q₁q₂ ist. Wir müssen zeigen, dass p ein Teiler von q₁ oder ein Teiler von q₂ ist, d. h. es gilt p = q₁ oder p = q₂. Wir dürfen hierzu keineswegs verwenden, dass das Produkt q₁q₂ lediglich die Primteiler q₁ und q₂ besitzt. Dies wollen wir ja gerade beweisen! Wir müssen zeigen, dass sich bei der Produktbildung q₁ q₂ keine Primfaktoren außer q₁ und q₂ hineinschmuggeln. Der Leser vergleiche hierzu das Gegenbeispiel der Menge G der geraden Zahlen aus dem letzten Essay. Hier schummelt sich der Primfaktor 6 in das Produkt 2 · 18 = 36 hinein. Die Zahl 36 hat in G die drei Primfaktoren 2, 6 und 18.

Wir diskutieren in diesem und im folgenden Essay zwei verschiedene Beweise des Lemmas von Euklid. Hier führen wir es auf ein weiteres für sich interessantes Lemma zurück:

Das Lemma von Bezout

Satz (Lemma von Bezout)

Seien a, b ≥ 1 natürliche Zahlen, und sei g = ggT(a, b) der größte gemeinsame Teiler von a und b. Dann ist g eine Linearkombination von a und b, d. h. es gibt ganze Zahlen λ und μ mit

g = λ a + μ b.

Wir betrachten einige Beispiele zur Illustration des Lemmas.

Beispiele

(1)	Seien a = 5 und b = 7. Dann ist g = 1 und 1 = 3 · 5 − 2 · 7. Damit ist die Zahl 1 eine Linearkombination von 5 und 7 mit den ganzzahligen Koeffizienten λ = 3 und μ = − 2.

(2)	Seien a = 102 und b = 45. Dann ist g = 3 und 3 = 4 · 102 − 9 · 45. Damit ist die Zahl 3 eine Linearkombination der Zahlen 102 und 45 mit den ganzzahligen Koeffizienten λ = 4 und μ = −9.

Der Leser wird sich vielleicht fragen, ob wir die Koeffizienten (speziell des zweiten Beispiels) raten oder durch Ausprobieren finden müssen oder ob wir sie berechnen können. Bevor wir uns dieser Frage zuwenden, zeigen wir:

Beweis des Lemmas von Euklid mit Hilfe des Lemmas von Bezout

Seien p, a, b wie in der Variante III des Lemmas von Euklid, d. h. es gelte:

(1)	p ist prim.

(2)	p ist ein Teiler des Produkts ab.

(3)	p ist kein Teiler von a.

Wir zeigen, dass p ein Teiler von b ist. Da p prim und kein Teiler von a ist, ist ggT(p, a) = 1. Nach dem Lemma von Bezout gibt es ganze Zahlen λ, μ mit

1 = λ p + μ a.

Multiplikation mit b liefert

b = λ p b + μ a b.

Nach Voraussetzung (2) ist p ein Teiler des Produkts ab, sodass ein d existiert mit ab = pd. Damit ist

b = λ p b + μ p d = p (λ b + μ d).

Dies zeigt, dass p ein Teiler von b ist.

Der Euklidische Algorithmus

Damit haben wir den Beweis des Lemmas von Euklid und damit den Beweis der Eindeutigkeit der Primfaktorzerlegung auf das Lemma von Bezout reduziert. Wie zeigt man nun aber das Lemma von Bezout? Sehr elegant lässt es sich mit Hilfe des Euklidischen Algorithmus beweisen. Wir verzichten hier auf eine formale Diskussion und erläutern das Vorgehen exemplarisch.

Der Euklidische Algorithmus berechnet den größten gemeinsamen Teiler zweier gegebener Zahlen a und b, indem er wiederholt die folgende Anweisung durchführt:

Ziehe die kleinere Zahl von der größeren ab.

Der Algorithmus stoppt, sobald die beiden Zahlen gleich geworden sind. Für das Paar (5, 7) erhalten wir zum Beispiel die Berechnung

(5, 7), (5, 2), (3, 2), (1, 2), (1, 1).

Der größte gemeinsame Teiler von 5 und 7 ist in der Tat 1. Äquivalent als Division mit Rest notiert lautet die Berechnung

7 = 1 · 5 + 2

5 = 2 · 2 + 1

2 = 2 · 1 + 0

In dieser Form können wir nun zurückrechnen, um die 1 als Linearkombination von 5 und 7 darzustellen. Beginnend mit der vorletzten Zeile erhalten wir:

1	= 5 − 2 · 2
	= 5 − 2 (7 − 1 · 5)
	= 3 · 5 − 2 · 7

Damit haben wir die Koeffizienten 3 und −2 des ersten obigen Beispiels gefunden. Für das zweite Beispiel mit a = 102 und b = 45 verläuft der Euklidische Algorithmus wie folgt:

(102, 45), (57, 45), (12, 45), (12, 33), (12, 21), (12, 9), (3, 9), (3, 6), (3, 3).

Damit ist die Zahl 3 der größte gemeinsame Teiler der Zahlen 102 und 45. Als Division mit Rest notiert liest sich die Berechnung:

102	= 2 · 45 + 12
45	= 3 · 12 + 9
12	= 1 · 9 + 3
9	= 3 · 3 + 0

Rückrechnen liefert

3	= 12 − 1 · 9
	= 12 − 1 · (45 − 3 · 12) = 4 · 12 − 1 · 45
	= 4 · (102 − 2 · 45) − 1 · 45
	= 4 · 102 − 9 · 45

Damit haben wir auch die Koeffizienten 4 und −9 des zweiten Beispiels gefunden.

Diese exemplarischen Berechnungen lassen sich in einen Beweis des Lemmas von Bezout überführen, der nicht nur das Lemma etabliert, sondern auch zeigt, dass sich die gesuchten Koeffizienten mit Hilfe des Euklidischen Algorithmus effektiv berechnen lassen. Wir verweisen den Leser auf die Literatur für die genaue Durchführung des Beweises.

Unsere Überlegungen zeigen, dass wir die Eindeutigkeit der Primfaktorzerlegung in einer systematischen Darstellung der elementaren Zahlentheorie wie folgt erreichen können:

(1)	Wir definieren den größten gemeinsamen Teiler zweier Zahlen.

(2)	Mit Hilfe des Euklidischen Algorithmus zeigen wir, wie sich der größte gemeinsame Teiler berechnen lässt (ohne Verwendung der Primfaktorzerlegung).

(3)	Durch „Rückrechnen“ erhalten wir aus dem Euklidischen Algorithmus das Lemma von Bezout.

(4)	Aus dem Lemma von Bezout erhalten wir das Lemma von Euklid.

(5)	Aus dem Lemma von Euklid ergibt sich die Eindeutigkeit der Primfaktorzerlegung.

Dieser Weg zum Fundamentalsatz der Zahlentheorie motiviert, die Teilbarkeitstheorie von vorne herein nicht nur über den natürlichen Zahlen ℕ, sondern allgemeiner über den ganzen Zahlen ℤ zu entwickeln. In den Linearkombinationen des Lemmas von Bezout tauchen negative Koeffizienten auf und wir können in den ganzen Zahlen freier rechnen.

Der Leser kann an diesem Beispiel den Prozess der Organisation des mathematischen Wissens verfolgen. Aus der logischen Ordnung der Ergebnisse ergibt sich ein natürlicher Fahrplan für die Darstellung einer Theorie. Den größten gemeinsamen Teiler und den Euklidischen Algorithmus können wir untersuchen, ohne Primzahlen zu betrachten − das Problem der effektiven Berechnung des ggT ist für sich interessant genug. Als Korollar dieser Untersuchung erhalten wir das Lemma von Bezout, das dann für einen Beweis der Eindeutigkeit der Primfaktorzerlegung zur Verfügung steht. Dies erklärt, warum in vielen Lehrbüchern zuerst der Euklidische Algorithmus und erst danach die Eindeutigkeit der Primfaktorzerlegung behandelt wird. Die Motivation dahinter ist für den Leser im Allgemeinen nicht mehr erkennbar. Das ist keineswegs ein Mangel, auch ein Autor eines Theaterstücks wird im Allgemeinen seinem Stück keine Diskussion beifügen, warum er es so geschrieben hat und nicht anders.