3.12 Vollständige Induktion
3.12.1 Das Grundprinzip der Induktion
In diesem Abschnitt behandeln wir das Prinzip der vollständigen Induktion, einer wichtigen Methode, um zu beweisen, dass eine Aussage für alle natürlichen Zahlen gilt. Betrachten Sie als Beispiel die Aussage
die für jede natürliche Zahl \(n\) sinnvoll ist. Man kann die Aussage in konkreten Fällen überprüfen – zum Beispiel ist \(7^3 - 7 = 343 - 7 = 336\) tatsächlich durch \(3\) teilbar. Aber wie würde man so etwas für alle \(n\) beweisen?
Das Induktionsprinzip gibt uns eine Methode dafür an die Hand. Formal ausgedrückt wird das in dem folgenden Satz:
Sei \(P(n)\) eine Eigenschaft, die die natürliche Zahl \(n\) haben oder nicht haben kann (oder: sei für jede natürliche Zahl \(n\) eine Aussage \(P(n)\) gegeben), so dass die folgenden beiden Bedingungen erfüllt sind:
\(P(0)\) ist wahr, und
für jede natürliche Zahl \(n\ge 1\) gilt: Wenn \(P(n-1)\) wahr ist, dann ist auch \(P(n)\) wahr.
Dann ist \(P(n)\) wahr für alle \(n\in \mathbb N\).
Oft wird die Aussage dieses Satzes als eines der Axiome eingesetzt, die für die natürlichen Zahlen angenommen werden. Jedenfalls ist klar, dass für seinen Beweis ein Axiom über die natürlichen Zahlen erforderlich ist, das darüber hinaus geht, dass jede natürliche Zahl \(\ne 0\) einen eindeutig bestimmten Nachfolger hat. Wir wollen hier vom Prinzip des kleinsten Elements ausgehen, das vielleicht eingängiger ist als das Induktionsprinzip:
Sei \(M = \{ n\in \mathbb N;\ P(n)\ \text{ist falsch}\} \). Wir wollen zeigen, dass \(M\) die leere Menge ist, denn das bedeutet gerade, dass \(P(n)\) für alle \(n\) wahr ist. Wenn \(M\) nicht leer ist, dann besitzt \(M\) nach dem Prinzip vom kleinsten Element ein kleinstes Element \(n\). Weil nach Voraussetzung \(P(0)\) wahr ist, kann nicht \(n=0\) sein. Dann ist aber \(n-1\not \in M\), weil \(n\) das kleinste Element von \(M\) ist. Also ist \(P(n-1)\) wahr, aber \(P(n)\) falsch. Das ist ein Widerspruch zu Teil (b) der Voraussetzung.
Um mit dem Prinzip der vollständigen Induktion eine Aussage über natürliche Zahlen zu beweisen, muss man also die Eigenschaften (a) und (b) in Satz 3.34 nachweisen. Dabei nennt man Teil (a) den Induktionsanfang und Teil (b) den Induktionsschritt. In den meisten Beweisen hier im Skript und in der Literatur werden die Wörter Induktionsanfang und Induktionsschritt aber gar nicht mehr hingeschrieben, sondern es wird normalerweise nur darauf hingewiesen, dass ein Induktionsbeweis folgt und dann werden die Fälle \(n=0\) und \(n{\gt}0\) betrachtet.
Behauptung. Für alle natürlichen Zahlen \(n\) gilt, dass \(n^3-n\) durch \(3\) teilbar ist.
Beweis durch vollständige Induktion nach \(n\).
Induktionsanfang \(n=0\): In diesem Fall gilt \(n^3 -n = 0^3 -0 =0\), und \(0 = 3\cdot 0\) ist ein Vielfaches von \(3\), mit anderen Worten: Durch \(3\) teilbar.
Induktionsschritt \(n{\gt}0\). Wir dürfen nun als Induktionsvoraussetzung annehmen, dass für \(n-1\) die Aussage gilt, das bedeutet, dass \((n-1)^3 - (n-1)\) durch \(3\) teilbar ist. Wir müssen zeigen, dass \(n^3-n\) ebenso ein Vielfaches von \(3\) ist.
Wir rechnen 1
Um zu sehen, dass das hilfreich ist, schreiben wir den letzten Ausdruck noch ein bisschen um:
Nun ziehen wir auf beiden Seiten \(3(n-n^2)\) ab und erhalten
Nach Induktionsvoraussetzung ist \((n-1)^3 - (n-1)\) ein Vielfaches von \(3\). Offensichtlich ist \(3(n^2-n)\) ein Vielfaches von \(3\). Deswegen ist auch die Summe, und das ist gerade \(n^3 -n\), ein Vielfaches von \(3\).□
In diesem Fall ist es nicht allzu schwierig, statt des Induktionsbeweises einen direkten Beweis zu finden, der nur die Eigenschaften natürlicher Zahlen benutzt, die wir als bekannt voraussetzen. Haben Sie eine Idee?
Wie ist es, wenn wir den Exponenten durch eine andere Zahl als \(3\) ersetzen? Für \(k\in \{ 2, 5, 7\} \) gilt: \(n^k -n\) ist ein Vielfaches von \(k\). Können Sie das beweisen? Für \(k=4\) ist diese Aussage nicht richtig. Finden Sie ein Gegenbeispiel? (Siehe Abschnitt 4.2.3.)
Statt im Induktionsschritt zu beweisen, dass für \(n{\gt}0\) die Aussage \(P(n)\) aus \(P(n-1)\) folgt, kann man natürlich genau so gut zeigen, dass für \(n\ge 0\) die Aussage \(P(n+1)\) aus \(P(n)\) folgt. (Schreiben Sie den Beweis des vorherigen Beispiels in diesem Stil um. Es ist dann vielleicht besser, zuerst den Ausdruck \((n+1)^3-(n-1)\) umzuformen.)
Wir haben das Induktionsprinzip schon benutzt (ohne es wirklich auszusprechen) im Beweis des Satzes, dass es unendlich viele Primzahlen gibt (Satz 3.6, vergleiche Beispiel 3.42 unten).
3.12.2 Varianten des Induktionsprinzips
Es gibt einige Abwandlungen des Prinzips der vollständigen Induktion:
Sei \(M\subseteq \mathbb N\) eine Teilmenge mit den Eigenschaften
\(0\in M\), und
für alle natürlichen Zahlen \(n\ge 1\) mit \(n-1\in M\) gilt \(n\in M\).
Dann gilt \(M = \mathbb N\).
Definiere \(P(n)\) als die Aussage \(P(n) : \Leftrightarrow \ n\in M\). Dann gilt \(P(0)\), und für alle \(n\in \mathbb N\) folgt aus \(P(n)\), dass \(P(n+1)\) gilt. Nach dem Prinzip der vollständigen Induktion ist \(P(n)\) für alle \(n\in \mathbb N\) eine wahre Aussage. Das besagt genau, dass \(M=\mathbb N\).
Statt des Axioms 3.35 könnte man auch einen der beiden Sätze als Axiom hernehmen, und dann die beiden anderen Aussagen daraus ableiten.
Manchmal sind die folgenden Varianten des Induktionsprinzips nützlich:
Sei \(n_0\in \mathbb N\) eine natürliche Zahl. Sei für alle \(n\ge n_0\) die Aussage \(P(n)\) gegeben. Es gelte:
\(P(n_0)\) ist wahr, und
für jede natürliche Zahl \(n{\gt} n_0\) gilt: Wenn \(P(n-1)\) wahr ist, dann ist auch \(P(n)\) wahr.
Dann ist \(P(n)\) wahr für alle natürlichen Zahlen \(n\ge n_0\).
Wir definieren die Aussage \(P^\prime (n)\) (für \(n\in \mathbb N\)) als \(P(n+n_0)\). Aus dem üblichen Induktionsprinzip folgt dann, dass \(P^\prime \) für alle \(n\in \mathbb N\) wahr ist. Das bedeutet, dass \(P(n)\) wahr ist für alle \(n\ge n_0\).
Behauptung. Für alle natürlichen Zahlen \(n\ge 5\) gilt \(2^n {\gt} n^2\).
Beweis per Induktion nach \(n\). Induktionsanfang: \(n=5\). Es gilt
Induktionsschritt: \(n {\gt} 5\). Wir müssen zeigen, dass aus der »Induktionsvoraussetzung« \(2^{n-1} {\gt} (n-1)^2\) folgt, dass \(2^n {\gt} n^2\). Wir rechnen dazu:
wobei wir die Induktionsvoraussetzung (für das erste \({\gt}\)) und die Abschätzung \(n{\gt}5\) (für das zweite \({\gt}\)) benutzt haben.
Man beachte, dass die Aussage \(2^n {\gt} n^2\) für \(n\le 4\) falsch ist.
Sei \(P(n)\) eine Eigenschaft, die die natürliche Zahl \(n\) haben oder nicht haben kann (oder: sei \(P(n)\) eine Aussage über alle natürlichen Zahlen \(n\)) mit den folgenden beiden Eigenschaften:
\(P(0)\) ist wahr, und
für jede natürliche Zahl \(n{\gt} 1\) gilt: Wenn \(P(0)\), \(P(1)\), …, \(P(n-1)\) alle wahr sind, dann ist auch \(P(n)\) wahr.
Dann ist \(P(n)\) wahr für alle \(n\in \mathbb N\).
Machen Sie sich klar, dass die Voraussetzung (b) in diesem Satz schwächer ist als in Satz 3.34, weil man auf mehr Informationen zurückgreifen kann, um \(P(n)\) zu zeigen. Der Satz ist also a priori stärker als Satz 3.34. (Man spricht manchmal von starker Induktion.) Das heißt: Es ist klar, dass die Aussage von Satz 3.34 aus Satz 3.41 folgen würde, aber wir müssen erst beweisen, dass es auch umgekehrt der Fall ist. Zum Glück ist das nicht schwierig.
Wir definieren für \(n\in \mathbb N\) die Aussage \(P^\prime (n)\) durch
Dann erfüllt \(P^\prime \) die Voraussetzungen des üblichen Induktionsprinzips (Satz 3.34) und daher gilt \(P^\prime (n)\) für alle \(n\). Damit folgt auch \(P(n)\) für alle \(n\), wie gewünscht.
Manchmal kombiniert man auch die beiden vorherigen Varianten:
Behauptung. Jede natürliche Zahl \(n\ge 2\) wird von einer Primzahl geteilt. (Vergleiche den Beweis von Satz 3.6)
Begründung. Induktionsanfang: \(n=2\). In diesem Fall ist die Aussage richtig, da \(2\) eine Primzahl und ein Teiler von sich selbst ist.
Induktionsschritt: \(n {\gt} 2\). Wir verwenden das Prinzip von Satz 3.41 und dürfen daher annehmen, dass die Aussage für alle natürlichen Zahlen \(m\) mit \(2\le m {\lt} n\) richtig ist. Wenn nun \(n\) eine Primzahl ist, dann ist die Sache klar. Ansonsten besitzt \(n\) eine Zerlegung als Produkt \(n = ab\) mit \(a, b {\gt} 1\). Dann gilt, dass \(2\le a {\lt} n\), also wird \(a\) nach Induktionsvoraussetzung von einer Primzahl geteilt. Als Teiler von \(a\) ist diese auch ein Teiler von \(n\), und wir sind fertig.
Auch einige Definitionen werden nach dem Induktionsprinzip vorgenommen, zum Beispiel definiert man (für Zahlen \(a_0\), …, \(a_n\) oder andere »Objekte«, für die eine Addition definiert ist) das Summensymbol \(\sum _{i=0}^n a_i\), das die Summe der \(a_i\) bezeichnen soll. (\(\Sigma \) ist der griechische Großbuchstabe Sigma.) Anschaulich, aber informell möchte man definieren
aber die Pünktchen auf der rechten Seite sind kein mathematisches Objekt (wir haben dieses Symbol jedenfalls nicht definiert). Als formale Definition für das Summensymbol setzen wir
Das Induktionsprinzip zeigt, dass dann \(\sum _{i=0}^n a_i\) für alle natürlichen Zahlen \(n\) definiert ist. Analog definiert man \(\sum _{i=m}^n a_i\), \(\sum _{i = -m}^n a_i\), usw.
Wenn in dem (Zahl-)Bereich, dessen Addition benutzt wird, das Kommutativgesetz und Assoziativgesetz der Addition gelten (also \(a+b=b+a\) und \((a+b)+c = a+(b+c)\) für alle \(a\), \(b\), \(c\)), so kommt es auf die Reihenfolge der Summanden nicht an und man kann für jede endliche Menge \(I\) und Familie \((a_i)_{i\in I}\) die Summe \(\sum _{i\in I} a_i\) definieren. Ist \(I = \emptyset \) so spricht man auch von der leeren Summe und definiert ihren Wert als \(0\). Das ist eine sinnvolle Konvention; zum Beispiel gilt dann für jede Indexmenge \(I\), Familie \((a_i)_{i\in I}\) und Teilmenge \(J\subseteq I\):
Analog zum Summenzeichen definiert man das Produktzeichen (Das Symbol \(\Pi \) ist das griechische große Pi.):
Auch hier kann man natürlich weitere Varianten definieren. Das leere Produkt \(\prod _{i\in \emptyset } a_i\) hat per Konvention den Wert \(1\).
Je nachdem, wie viel Lust/Interesse Sie daran haben, zu diesem Zeitpunkt auch »offensichtliche« Eigenschaften der ganzen Zahlen formal zu beweisen, können Sie diese ergänzende Bemerkung lesen oder überspringen.
Sei \(n\in \mathbb Z\) eine ganze Zahl. Wir sagen, eine ganze Zahl \(d\in \mathbb Z\) sei ein Teiler von \(n\) (oder \(d\) teile \(n\)), wenn eine ganze Zahl \(k\in \mathbb Z\) existiert mit \(n = dk\). Wir schreiben dann \(d\, |\, n\), gesprochen »\(d\) teilt \(n\)«.
Eine Primzahl ist eine ganze Zahl \(p {\gt} 1\), deren einzige positive Teiler \(1\) und \(p\) selbst sind.
Wenn \(d\) kein Teiler von \(n\) ist, drücken wir das in Symbolen aus als \(d\nmid n\). Zum Beispiel gilt für alle \(n\in \mathbb Z\): \(1\, |\, n\), \(-1\, |\, n\), \(n\, |\, n\), \(n\, |\, 0\). Wenn \(n\ne 0\) ist, dann gilt \(0\nmid n\).
Einige weitere Eigenschaften der Teilbarkeit sind in dem folgenden Satz gesammelt. Wir schreiben dabei \(|a|\) für den Absolutbetrag (manchmal sagt man einfach Betrag) einer (reellen) Zahl \(a\). Ist \(a\ge 0\), so ist \(|a| := a\), ist \(a {\lt} 0\), so setzt man \(|a| := -a\). In jedem Fall gilt also \(|a| \ge 0\).
Seien \(a\), \(b\), \(c\) ganze Zahlen.
Gilt \(a\, |\, b\) und \(b\ne 0\), so gilt \(|a|\le |b|\). Gilt \(a\, |\, b\) und \(a, b {\gt} 0\), so gilt \(a\le b\).
Aus \(a\, |\, b\) und \(b\, |\, c\) folgt \(a\, |\, c\).
Gilt \(a\, |\, b\) und \(b\, |\, a\), so ist \(a=b\) oder \(a=-b\).
Gilt \(a\, |\, b\) und \(a\, |\, c\), so gilt \(a\, |\, (b+c)\) und \(a\, |\, (b-c)\).
Alle diese Aussagen sind leicht zu beweisen. Versuchen Sie es als erstes selbst einmal!
zu (1). Wenn \(b = ka\) und \(b\ne 0\), so folgt \(|k|\, |a| = |ka| = |b|\) und damit \(|a| \le |b|\). Wenn sogar \(a\) und \(b\) beide positiv sind, dann muss auch \(k\) positiv sein, d.h. \(k\ge 1\). Daraus folgt \(b = ak \ge a\).
zu (2). Gilt \(b = ka\) und \(c = lb\), so folgt \(c = (kl)a\), also \(a\, |\, c\).
zu (3). Gilt \(b = ka\) und \(a = l b\), so folgt \(a = (kl)a\), also \(a (kl -1) = 0\). Weil das Produkt \(a(kl-1)\) Null ist, muss einer der Faktoren Null sein. Ist \(a=0\), so folgt \(b=ka=0\), also \(a=b\). Ist \(kl=1\), so muss \(k=l=1\) oder \(k=l=-1\) sein, denn \(k\) und \(l\) sind ganze Zahlen. Daraus folgt die Behauptung.
zu (4). Gilt \(b = ka\) und \(c=la\), so folgt \(b+c = (k+l)a\) und \(b-c = (k-l)a\). Das zeigt die Behauptung.
Zuerst zeigen wir die Eindeutigkeit: Gilt \(x=qn+r = q^\prime n+r^\prime \) mit \(0\le r, r^\prime {\lt} n\), so folgt \((q-q^\prime )n + (r-r^\prime ) = x-x =0\). Weil \(|r-r^\prime | {\lt} n\) ist, folgt \(|q-q^\prime |\cdot |n| = |r-r^\prime | {\lt} n\) und daraus \(q-q^\prime =0\), also \(q=q^\prime \) und damit auch \(r=r^\prime \).
Es bleibt noch die Existenz der Zahlen \(q\) und \(r\) zu zeigen. Wir betrachten zunächst den Fall \(x\ge 0\) und führen Induktion nach \(x\). Für \(x = 0\) setzen wir \(q=r=0\).
Ist \(x{\gt}0\), so können wir per Induktionsvoraussetzung annehmen, dass wir \(x-1\) in der Form \(q^\prime n+r^\prime \) schreiben können, mit \(0\le r^\prime {\lt} n\). Ist \(r^\prime \) sogar kleiner als \(n-1\), so setzen wir \(q=q^\prime \), \(r=r^\prime +1\). Dann gilt \(n = (n-1)+1 = q^\prime n + r^\prime +1 = qn+r\) und \(0\le r {\lt} n\), wie gewünscht. Sonst ist \(r^\prime =n-1\), und dann können wir \(q=q^\prime +1\) und \(r=0\) setzen.
Ist \(x {\lt} 0\), so können wir das schon Bewiesene auf \(-x\) anwenden und erhalten \(-x = q^\prime n + r^\prime \) für Zahlen \(q^\prime \), \(r^\prime \) mit \(0\le r^\prime {\lt} n\). Ist \(r^\prime = 0\), so folgt \(x = -q^\prime n\) und wir setzen \(q=-q^\prime \), \(r=0\). Ist \(r^\prime {\gt} 0\), so gilt \(x = -q^\prime n - r^\prime = (-q^\prime -1)n + n-r^\prime \) und wir können \(q=-q^\prime -1\) und \(r = n-r^\prime {\lt} n\) setzen.
Es gibt natürlich die Möglichkeit, den Satz auf den Fall \(n {\lt} 0\) zu verallgemeinern (mit der Bedingung \(0 \le r {\lt} |n|\)).
Seien \(a, b\) ganze Zahlen. Eine Zahl \(d\in \mathbb Z\) heißt ein gemeinsamer Teiler von \(a\) und \(b\) wenn \(d\, |\, a\) und \(d\, |\, b\).
Das größte Element der Menge aller gemeinsamen Teiler von \(a\) und \(b\) heißt der größte gemeinsame Teiler von \(a\) und \(b\), geschrieben \(\operatorname{ggT}(a, b)\) (sofern nicht \(a=b=0\) gilt).
Sind \(a=b=0\), so ist jede ganze Zahl ein gemeinsamer Teiler von \(a\) und \(b\), weswegen wir diesen Fall oben ausschließen. Wir definieren \(\operatorname{ggT}(0,0)=0\).
Da für jeden Teiler \(d\) einer Zahl \(a\ne 0\) gilt, dass \(|d| \le |a|\), haben \(a\) und \(b\) nur endlich viele gemeinsame Teiler, wenn nicht \(a=b=0\) gilt, und daher hat die Menge der gemeinsamen Teiler tatsächlich ein größtes Element.
Die gemeinsamen Teiler von \(24\) und \(45\) sind \(-3, -1, 1, 3\), also \(\operatorname{ggT}(24, 45) = 3\).
Wir halten noch die folgenden Eigenschaften des größten gemeinsamen Teilers fest:
Seien \(a, b\in \mathbb Z\).
Es gilt \(\operatorname{ggT}(a, b ) = \operatorname{ggT}(-a, b) = \operatorname{ggT}(a, -b) = \operatorname{ggT}(-a, -b)\).
Es gilt \(\operatorname{ggT}(a, b) = \operatorname{ggT}(a-b, b)\).
zu (1). Dies ist klar, da die Teiler von \(a\) mit den Teilern von \(-a\) übereinstimmen (und ebenso für \(b\)).
zu (2). Wir zeigen, dass die Menge der gemeinsamen Teiler von \(a\) und \(b\) übereinstimmt mit der Menge der gemeinsamen Teiler von \(a-b\) und \(b\). Daraus folgt die Behauptung.
Ist \(d\) eine Zahl mit \(d\, |\, a\), \(d\, |\, b\), so folgt mit Satz 3.46 (4), dass \(d\, |\, a-b\). Also ist \(d\) ein gemeinsamer Teiler von \(a-b\) und \(b\).
Ist umgekehrt \(d\) eine ganze Zahl mit \(d\, |\, a-b\) und \(d\, |\, b\), so folgt mit demselben Lemma, dass \(d \, |\, (a-b)+b = a\).
Zum Berechnen des größten gemeinsamen Teilers verwendet man den Euklidischen Algorithmus.
In dieser Ergänzung beweisen wir den Satz über die eindeutige Primfaktorzerlegung in den ganzen Zahlen. Der entscheidende Punkt ist die folgende Eigenschaft von Primzahlen:
Um den Satz zu beweisen, benutzen wir das folgende Lemma.
Sind \(a, b\in \mathbb Z\), so existieren \(x, y\in \mathbb Z\) mit
Wegen Lemma 3.50 (1) können wir gegebenenfalls \(a\) und/oder \(b\) durch ihr Negatives ersetzen und daher annehmen, dass \(a, b\ge 0\). Ist eine der Zahlen \(a\), \(b\) gleich Null, so ist die Aussage von vorneherein klar. Wir können daher sogar voraussetzen, dass \(a, b {\gt} 0\).
Wir führen nun Induktion nach der Zahl \(\max (a, b)\), dem Maximum von \(a\) und \(b\). Ist dieses \(=1\), so gilt \(a = b = 1\) und \(\operatorname{ggT}(a, b ) = 1\), und wir nehmen \(x=1\), \(y=0\).
Sei nun \(\max (a,b){\gt}1\). Ohne Einschränkung sei \(a\ge b\) (sonst vertauschen wir einfach \(a\) und \(b\).) Gilt \(a=b\), so ist \(\operatorname{ggT}(a,b)=a\) und wir können wieder \(x=1\), \(y=0\) setzen. Sonst gilt \(a-b, b\ge 1\) und \(\max (a-b,b) {\lt} \max (a,b)\). Dann erhalten wir
für geeignete ganze Zahlen \(x^\prime , y^\prime \), wobei wir für die erste Gleichheit Lemma 3.50 und für die zweite die Induktionsvoraussetzung verwenden. Wir setzen also \(x:= x^\prime \), \(y:=y^\prime - x^\prime \) und erhalten das gewünschte Ergebnis.
Sei \(p\) eine Primzahl und seien \(a, b\in \mathbb Z\) mit \(p\, |\, ab\). Wenn \(p\) nicht \(a\) teilt, dann gilt \(\operatorname{ggT}(p,a) = 1\) (denn die einzigen positive Teiler von \(p\) sind ja nach Definition einer Primzahl \(1\) und \(p\)).
Nach dem Lemma können wir also \(x, y\in \mathbb Z\) finden mit
also
Nun werden \(xpb\) (offensichtlich) und \(yab\) (nach Voraussetzung) von \(p\) geteilt, also auch ihre Summe: \(p\, |\, b\).
Es ist nicht schwer zu sehen, dass jede ganze Zahl \(p {\gt} 1\) mit der Eigenschaft, dass \(p\, |\, ab \Rightarrow p\, |\, a\ \text{oder} p\, |\, b\) eine Primzahl ist.
In der Tat, wenn \(p\) diese Eigenschaft hat und \(p = ab\) gilt, dann gilt ja erst recht \(p\, |\, ab\), also \(p\, |\, a\) oder \(p\, |\, b\), und wenn zum Beispiel \(p\, |\, a\) gilt, so folgt \(ab = p \le |a|\), also \(b=1\) oder \(b=-1\) und damit \(a=p\) oder \(a=-p\).
Sei \(p\) eine Primzahl, und seien \(a_1, \dots , a_n\) ganze Zahlen. Wenn \(p\) das Produkt \(a_1\cdot \cdots \cdot a_n\) teilt, dann teilt \(p\) (mindestens) einen der Faktoren \(a_i\).
Dies folgt aus dem Satz über die Primeigenschaft und einer einfachen Induktion.
Sei \(a\ne 0\) eine ganze Zahl. Dann gibt es \(n\ge 0\) und Primzahlen \(p_1, \dots , p_n\in \mathbb Z\), so dass
wobei \(\varepsilon = 1\), wenn \(a{\gt}0\), und \(\varepsilon = -1\), wenn \(a {\lt} 0\) ist. Dabei sind die Primzahlen \(p_i\) bis auf ihre Reihenfolge eindeutig bestimmt.
Für den Fall, dass \(a=1\) oder \(a=-1\) ist, verstehen wir die Aussage so, dass \(a\) als Produkt von \(\varepsilon = 1\) (bzw. \(\varepsilon =-1\)) und dem »leeren Produkt«, dessen Wert \(1\) ist, geschrieben wird. Man beachte, dass die \(p_i\) in der Aussage des Satzes in der Regel nicht paarweise verschieden sein werden. Insbesondere geht die Eindeutigkeitsaussage darüber hinaus zu behaupten, dass die Menge \(\{ p_1, \dots , p_n\} \) der Primzahlen, die im Produkt überhaupt auftreten, eindeutig bestimmt sei; auch die Anzahl der Faktoren, die gleich einer gegebenen Primzahl sind, ist eindeutig bestimmt.
(Aus dem Satz 3.52 über die Primeigenschaft folgt, dass \(\{ p_1, \dots , p_n\} \) genau die Menge der Primzahlen ist, die \(a\) teilen.)
Es ist klar, dass es ausreicht, den Fall \(a{\gt}0\) zu behandeln, weil sich der andere Fall leicht daraus ableiten lässt.
Existenz der Zerlegung. Wir zeigen die Existenz durch vollständige Induktion nach \(a\). Für \(a=1\) ist nach der obigen Bemerkung über die Interpretation der Aussage in diesem Fall nichts mehr zu zeigen. Sei nun also \(a{\gt}1\). Wir haben in Beispiel 3.42 gesehen, dass es eine Primzahl \(p\) gibt, die \(a\) teilt, etwa \(a = pk\). Nach Induktionsvoraussetzung lässt sich \(k\) als ein Produkt von Primzahlen schreiben. Indem wir den Faktor \(p\) hinzufügen, erhalten wir eine entsprechende Darstellung von \(a\).
Eindeutigkeit der Zerlegung. Wir wenden wiederum Induktion nach \(a\) an, wobei der Fall \(a=1\) klar ist. Betrachten wir eine Gleichheit der Form
für Primzahlen \(p_i\), \(q_j\). Wir müssen zeigen, dass \(m=n\) und dass jede Primzahl auf der linken Seite genauso oft vorkommt, wie auf der rechten Seite.
Da \(a{\gt}1\) ist, muss \(m\ge 1\) (und \(n\ge 1\)) gelten. Nun gilt \(p_m | p_1\cdot \cdots \cdot p_m = q_1\cdot \cdots \cdot q_n\), die Primzahl \(p_m\) teilt also das Produkt \(q_1\cdot \cdots \cdot q_n\). Wegen Korollar 3.55 gibt es ein \(i\in \{ 1, \dots , n\} \) mit \(p_m \, |\, q_i\). Weil \(p_m\) und \(q_i\) Primzahlen sind, muss \(p_m = q_i\) gelten. Weil wir uns nur für die Eindeutigkeit der Faktoren bis auf ihre Reihenfolge interessieren, können wir die \(q\)’s so umnummerieren, dass \(i=n\) ist; das vereinfacht die Notation ein bisschen.
Es gilt dann also \(p_m = q_n\) und daher auch
Auf dieses Produkt können wir die Induktionsvoraussetzung anwenden, das heißt: \(m-1 = n-1\), und die Familien \(p_1, \dots , p_{m-1}\) und \(q_1, \dots , q_{n-1}\) unterscheiden sich höchstens durch ihre Reihenfolge. Damit sind wir fertig.
Vermutlich kennen Sie die Aussage dieses Satzes schon seit langem und halten sie für klar. Jedenfalls wird sie meistens in der Schule irgendwann angegeben. Oftmals wird aber nicht darauf hingewiesen, dass sie keineswegs selbstverständlich ist. Die Existenz einer solchen Zerlegung ist dabei noch recht eingängig, denn man kann ja, wie wir es auch im Beweis tun, jede Zahl immer weiter aufspalten, bis man es nur noch mit Primzahlen als Faktoren zu tun hat. Warum man aber eine Zahl wie \(244\, 609\) nur in der einen Weise \(244\, 609 = 331\cdot 739\) (oder eben \(= 739\cdot 331\)) als Produkt von Primzahlen geschrieben werden kann und es nicht noch andere Möglichkeiten geben könnte, ist nicht offensichtlich.