Eindeutigkeit der Primfaktorzerlegung

 Eine Primfaktorzerlegung einer Zahl n ≥ 2 ist eine Darstellung von n als Produkt von Primzahlen. Die Primzahlen erscheinen bei dieser Betrachtung als die „multiplikativen Bausteine“ der natürlichen Zahlen. So ist zum Beispiel:

4  =  22,  6  =  2 · 3,  9  =  32,  15  =  3 · 5,  16  =  24,  18  =  2 · 32,  …

Um eine Primfaktorzerlegung von n zu finden, argumentieren wir induktiv. Für n = 2 ist die Aussage klar. Für ein n > 2 überprüfen wir für alle d mit 2 ≤ d < n der Reihe nach, ob d|n gilt oder nicht. Ist kein d ein Teiler von n, so ist n eine Primzahl (und eine Primfaktorzerlegung von sich selbst). Finden wir dagegen ein erstes d mit d|n, so ist d eine Primzahl und d · Z eine Primfaktorzerlegung von n, wobei Z eine nach Induktionsvoraussetzung existierende Primfaktorzerlegung von n/d < n ist.

 Stärker gilt: Ist p ein Primteiler von n, so existiert eine Primfaktorzerlegung von n, in der p vorkommt (nämlich p · Z mit Z Primfaktorzerlegung von n/p).

 Wie eine Faktorisierung von n effektiv durchgeführt werden kann, ist eine interessante Frage, die aber auf einem anderen Blatt steht.

 Es ist keineswegs selbstverständlich, dass eine Primfaktorzerlegung bis auf die Reihenfolge der Faktoren eindeutig ist. Der klassische Beweis ruht auf der folgenden Beobachtung:

Satz (Teilbarkeitssatz von Euklid)

Sei p prim, und seien a, b derart, dass p|ab. Dann gilt p|a oder p|b.

Beweis

Gilt p|a, so ist nichts weiter zu zeigen. Sei also p kein Teiler von a.

Dann ist ggT(p, a) = 1. Nach (G8) gilt also p|b.

 Wir geben für diesen wichtigen Satz noch einen etwas direkteren Beweis mit Hilfe von Linearkombinationen.

Direkter Beweis des Teilbarkeitssatzes

Ist p kein Teiler von a, so gilt ggT(p, a) = 1. Also existieren n, m mit

np  +  ma  =  1,  und damit gilt  npb  +  mab  =  b.

Wegen p|ab gibt es ein k mit ab = kp. Also gilt p(nb  +  mk)  =  b,  und folglich ist p ein Teiler von b.

 Problemlos ergibt sich folgende Verallgemeinerung:

Satz (allgemeiner Teilbarkeitssatz)

Sei p eine Primzahl, und seien a1, …, an mit n ≥ 1 derart, dass p|a1 · … · an.

Dann gibt es ein i mit p|ai.

Beweis

Wir zeigen die Aussage durch Induktion nach n. Für n = 1 ist nichts zu zeigen, und für n = 2 haben wir die Aussage bereits bewiesen. Gilt nun p|(a1 … an + 1) mit n ≥ 2, so setzen wir a = a1 … an. Dann gilt p|aan + 1 und damit p|a oder p|an + 1. Im zweiten Fall sind wir fertig, und im ersten Fall gibt es wegen a = a1 … an nach Induktionsvoraussetzung ein i mit p|ai.

 Mit anderen Worten: Teilt eine Primzahl ein Produkt, so teilt sie mindestens einen Faktor des Produkts. Daraus folgt sofort:

Korollar

Ist p eine Primzahl und gilt p|n, so kommt p in jeder Primfaktorzerlegung von n vor.

 Damit können wir nun den „Fundamentalsatz der Zahlentheorie“ zeigen:

Satz (Eindeutigkeit der Primfaktorzerlegung)

Jedes n ≥ 2 lässt sich eindeutig schreiben in der Form

n  =  p1e1 · … · pkek,

mit Primzahlen p1 < … < pk, k ≥ 1, und Exponenten ei ≥ 1.

Beweis

Wir zeigen die Behauptung durch starke Induktion nach n ≥ 2.

Induktionsschritt n

Sei p der kleinste Primteiler von n. Ist n = p, so ist die Aussage trivial.

Sei also n > p, und seien Z1 und Z2 Primfaktorzerlegungen von n wie im Satz. Nach dem Korollar kommt p in beiden Zerlegungen vor.

Nach Induktionsvoraussetzung stimmen dann aber die Zerlegungen Z1′ und Z2′ von n/p überein, die aus Z1 und Z2 durch Verminderung des p-Exponenten um 1 hervorgehen. Dann stimmen aber offenbar auch Z1 und Z2 überein.

Definition (kanonische Primfaktorzerlegung)

Sei n ≥ 2. Dann heißt die Darstellung n = p1e1 · … · pkek mit p1 < … < pk und Exponenten ei ≥ 1 die kanonische Primfaktorzerlegung von n.

 Anhand der kanonischen Primfaktorzerlegung von n lassen sich alle Teiler von n leicht ablesen. Ebenso können wir den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache von n und m sofort ermitteln, wenn die Primfaktorzerlegungen von n und m bekannt sind. Im Allgemeinen ist aber die Berechnung der Primfaktorzerlegung einer Zahl sehr aufwendig, und der Euklidische Algorithmus bleibt die erste Wahl zur Berechnung des größten gemeinsamen Teilers. Die Gleichung n m = ggT(n, m) · kgV(n, m) liefert dann auch das kleinste gemeinsame Vielfache.

 Wir geben noch einen weiteren Beweis der Eindeutigkeit der Primfaktorzerlegung, der den Teilbarkeitssatz nicht heranzieht. Dieser Beweis ist erst Anfang des 20. Jahrhunderts von Ernst Zermelo gefunden worden. Er ist ein Paradebeispiel für eine geistreiche starke Induktion.

Zweiter Beweis der Eindeutigkeit der Primfaktorzerlegung

Wir zeigen die Behauptung durch starke Induktion nach n ≥ 2.

Induktionsschritt n

Annahme, es gibt zwei verschiedene kanonische Primfaktorzerlegungen

p1e1 · … · pkek  =  n  =  q1d1 · … · qk′dk′.

Dann ist jedes pi verschieden von jedem qj, da wir sonst zwei unterschiedliche kanonische Primfaktorzerlegungen von n/pi = n/qj < n gewinnen könnten.

Ohne Einschränkung sei p1 < q1. Dann gilt p1q1 < q12 ≤ n (denn es gilt d1 ≥ 2 oder k′ ≥ 2, da n keine Primzahl sein kann). Also ist

m  =  n  −  p1q1  >  0.

Wegen p1|n und q1|n sind p1 und q1 Teiler von m. Dann kommen aber sowohl p1 als auch q1 in der nach Induktionsvoraussetzung eindeutigen kanonischen Primfaktorzerlegung von m < n vor. (Wegen p1|m und q1|m gibt es Primfaktorzerlegungen von m, in denen p1 bzw. q1 auftauchen; aufgrund der Eindeutigkeit folgt die Behauptung.) Also gilt p1q1|m, und damit p1q1|n. Also ist q1 ein Teiler von n/p1, und damit existiert eine Primfaktorzerlegung von n/p1, in der q1 vorkommt. Aber es gilt

n/p1  =  p1e1 − 1 · … · pkek.

Wegen n/p1 < n ist nach Induktionsvoraussetzung also q1 eine der Primzahlen pi, Widerspruch.

Irrationale Verhältnisse

 Als eine Anwendung der Eindeutigkeit der Primfaktorzerlegung zeigen wir die Existenz irrationaler Zahlen: Es gibt eine reelle Zahl x, die sich nicht als Bruch a/b mit ganzen Zahlen a, b, b ≠ 0, schreiben lässt. Konkret zeigen wir, dass x = 2, die positive Quadratwurzel aus 2, eine irrationale Zahl ist. Diese Aussage können wir formulieren, ohne den Bereich der ganzen Zahlen zu verlassen. Denn die Irrationalität dieser Wurzel können wir ausdrücken als:

Für alle natürlichen Zahlen a, b ≥ 1 ist (a/b)2 ≠ 2.

Gleichwertig hierzu ist wiederum die Aussage des folgenden Satzes:

Satz (Irrationalität von 2)

Es gibt keine ganzen Zahlen a, b ≥ 1 mit a2 = 2 · b2.

Beweis

Annahme doch. Seien a = 2e1 · u1  und  b = 2e2 · u2, mit ungeraden Zahlen u1, u2 und e1, e2 ≥ 0. Wegen a2 = 2 · b2 gilt dann:

(+)  a2  =  22 e1 · u12  =  22 · e2 + 1 · u22.

Dann ist 2 e1 gerade, aber 2 e2 + 1 ungerade. Also ist 2 e1 ≠ 2 · e2 + 1.

Aber die Zahlen u12 und u22 sind ungerade, und damit liefert (+) zwei verschiedene kanonische Primfaktorzerlegungen von a2, nämlich

a2  =  22 e1 · Z1  =  22 · e2 + 1 · Z2,

mit kanonischen Primfaktorzerlegungen Z1 von u12 und Z2 von u22, in denen der Faktor 2 nicht vorkommt. Widerspruch.

 Kurz: a2 = 2 · b2 ist für ganze Zahlen unmöglich, denn der 2-Exponent der eindeutigen Primfaktorzerlegung von a2 ist gerade (möglicherweise 0), der von 2 · b2 aber ungerade. Oder noch einmal anders formuliert: a2 können wir geradzahlig oft halbieren, 2 b2 ungeradzahlig oft.

 Die Irrationalität der Quadratwurzel aus 2 taucht häufig ganz vorne in Listen der wichtigsten oder schönsten mathematischen Resultate aller Zeiten auf. Jeder Mathematiker sollte davon wissen, und fast möchte man sagen, dass jeder davon wissen sollte, denn nicht zuletzt ist das Ergebnis auch kulturgeschichtlich von großer Bedeutung. Es widerlegte die Pythagoreische Doktrin „Alles ist Zahl“ im Sinne von „Jede Größe ist ein Verhältnis positiver natürlicher Zahlen“. Modern formuliert lautet die Doktrin, dass die rationalen Zahlen genügen, um ein mathematisches Kontinuum zu bilden. Die Irrationalität der Quadratwurzel aus 2 zeigt, dass ein mathematisches Kontinuum mehr Punkte umfassen muss als die rationalen Zahlen.