Ganze Zahlen/Hauptsatz über Primfaktorzerlegung/Euklid/Textabschnitt

Wir möchten nun zur Primfaktorzerlegung, deren Existenz wir bereits in Fakt gezeigt haben, beweisen, dass sie eindeutig ist. Natürlich kann man

${}12=3\cdot 2\cdot 2=2\cdot 3\cdot 2=2\cdot 2\cdot 3\,$

schreiben, mit eindeutig ist also eindeutig bis auf die Reihenfolge gemeint. Um dies zu zeigen brauchen wir zunächst das sogenannte Lemma von Euklid, das eine wichtige Eigenschaft einer Primzahl beschreibt.

Satz

Es sei ${}p$ eine Primzahl und ${}p$ teile ein Produkt ${}ab$ von natürlichen Zahlen ${}a,b\in \mathbb {N}$.

Dann teilt ${}p$ einen der Faktoren.

Beweis

Wir setzen voraus, dass ${}a$ kein Vielfaches von ${}p$ ist (andernfalls sind wir fertig). Dann müssen wir zeigen, dass ${}b$ ein Vielfaches von ${}p$ ist. Unter der gegebenen Voraussetzung sind ${}a$ und ${}p$ teilerfremd. Nach dem Lemma von Bezout gibt es ganze Zahlen ${}r,s$ mit

${}ra+sp=1\,$

Da ${}ab$ ein Vielfaches von ${}p$ ist, gibt es ein ${}t$ mit

${}ab=tp\,.$

Daher ist

${}b=b\cdot 1=b(ra+sp)=abr+bsp=tpr+bsp=p{\left(tr+bs\right)}\,.$

Also ist ${}b$ ein Vielfaches von ${}p$.

$\Box$

Aus dem Lemma von Euklid folgt sofort die etwas stärkere Aussage: Wenn eine Primzahl ${}p$ ein beliebiges Produkt ${}a_{1}a_{2}{\cdots }a_{n}$ teilt, dann teilt ${}p$ mindestens einen Faktor. Man wendet das Lemma einfach auf ${}(a_{1}a_{2}{\cdots }a_{n-1})\cdot a_{n}$ an (formal ist das eine Induktion über die Anzahl der Faktoren). Dies wird im Beweis des folgenden Hauptsatzes der elementaren Zahlentheorie verwendet.

Satz

Jede natürliche Zahl ${}n\in \mathbb {N}$, ${}n\geq 2$, besitzt eine eindeutige Zerlegung in Primfaktoren.

D.h. es gibt eine Darstellung

${}n=p_{1}{\cdots }p_{r}\,$

mit Primzahlen ${}p_{i}$, und dabei sind die Primfaktoren bis auf ihre Reihenfolge eindeutig bestimmt.

Beweis

Die Existenz der Primfaktorzerlegung wurde bereits in Fakt gezeigt. Die Eindeutigkeit wird durch Induktion über ${}n$ gezeigt. Für ${}n=2$ liegt eine Primzahl vor. Sei nun ${}n\geq 3$ und seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir

${}n=p_{1}{\cdots }p_{r}=q_{1}{\cdots }q_{s}\,.$

Wir müssen zeigen, dass nach Umordnung die Primfaktorzerlegungen übereinstimmen. Die Gleichheit bedeutet insbesondere, dass die Primzahl ${}p_{1}$ das Produkt rechts teilt. Nach Fakt muss dann ${}p_{1}$ einen der Faktoren rechts teilen. Nach Umordnung können wir annehmen, dass ${}q_{1}$ von ${}p_{1}$ geteilt wird. Da ${}q_{1}$ selbst eine Primzahl ist, folgt, dass ${}p_{1}=q_{1}$ sein muss. Daraus ergibt sich durch Kürzen, dass

${}p_{2}{\cdots }p_{r}=q_{2}{\cdots }q_{s}\,$

ist. Nennen wir diese Zahl ${}n'$. Da ${}n'<n$ ist, können wir die Induktionsvoraussetzung auf ${}n'$ anwenden und erhalten, dass links und rechts die gleichen Primzahlen stehen. 

$\Box$

In der kanonischen Primfaktorzerlegung schreibt man die beteiligten Primzahlen in aufsteigender Reihenfolge mit ihrem jeweiligen Exponenten, also beispielsweise

${}840=2^{3}\cdot 3\cdot 5\cdot 7\,.$

Damit ist insbesondere zu jeder ganzen Zahl ${}n\neq 0$ und jeder Primzahl ${}p$ eindeutig bestimmt, ob ${}p$ in der Primfaktorzerlegung überhaupt vorkommt und wenn ja mit welchem Exponenten.