Primfaktorisierung und der Satz von Euklid.

primfaktorisierung.md

Primfaktorisierung und der Satz von Euklid

Angenommen, $a$ und $b$ sind zwei positive ganze Zahlen. In der Schule haben wir gelernt, wie man $a$ durch $b$ teilt, durch Division. Dabei erhalten wir zwei eindeutige ganze Zahlen $q$ und $r$, den Quotienten und den Rest der Division, so dass $a = qb + r$, $q \geq 0$ und $0 \leq r < b$. Wenn der Rest $r=0$ ist, nennen wir $b$ einen Teiler von $a$ und sagen, dass $a$ durch $b$ teilbar ist oder dass $b$ die Zahl $a$ teilt. Eine Primzahl ist eine ganze Zahl $p \geq 2$, deren einzige Teiler $1$ und $p$ selbst sind. Die ersten zehn Primzahlen sind $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$. Eine positive ganze Zahl $n$, die nicht prim ist, wird zusammengesetzt genannt. Nach Definition muss sie einen Teiler $b$ zwischen $1$ und $n$ haben, was bedeutet, dass sie als Produkt ab von ganzen Zahlen $a$ und $b$ geschrieben werden kann, wobei $1 < a < n$ und $1 < b < n$ gilt. Seien $p_1, p_2, …, p_k$ Primzahlen, die $p1 \leq p_2 \leq \ldots \leq p_k$ erfüllen. Ihr Produkt wird als Primfaktorisierung der Zahl $n = p_1 \cdot p_2 \cdots p_k$ bezeichnet und die Primzahlen $p_1, \ldots, p_k$ werden als Primfaktoren von $n$ bezeichnet. Beachten Sie, dass es zur Definition einer Primfaktorisierung gehört, dass die Primfaktoren von links nach rechts in aufsteigender Reihenfolge geschrieben werden (wobei die gleiche Primzahl mehrmals im Produkt auftauchen kann). Das Ziel dieser ist es nun, den folgenden Satz zu beweisen:

Primfaktorisierungssatz, Fundamentalsatz der Arithmetik oder Satz von Euklid: Jede Ganzzahl $n > 1$ hat eine eindeutige Primfaktorisierung.

Um diesen Satz zu beweisen benötigen wir ein paar Lemmata als Zwischenergebnis:

Lemma: Jede ganze Zahl $n > 1$ ist das Produkt (von möglicherweise nur einer einzigen) Primzahl.

Beweis: Angenommen, die Behauptung ist falsch. Dann gibt es mindestens eine ganze Zahl größer als $1$, die nicht gleich einem Produkt von Primzahlen ist. Sei $m$ die kleinste solche Zahl. Da $m$ kein Produkt von Primzahlen ist, kann $m$ nicht prim sein und muss zusammengesetzt sein. Es gibt also ganze Zahlen $a$ und $b$, sodass $m = ab$, $1 < a < m$ und $1 < b < m$. Da $m$ die kleinste Zahl größer als $1$ war, die nicht gleich einem Produkt von Primzahlen war, müssen sowohl $a$ als auch $b$ gleich Produkten von Primzahlen sein, was bedeutet, dass $m = ab$ letztendlich doch gleich einem Produkt von Primzahlen sein muss. Widerspruch. $\blacksquare$

Das Lemma besagt, dass jede ganze Zahl größer als $1$ gleich einem Produkt von Primzahlen ist und daher eine Primfaktorzerlegung hat (schreiben Sie einfach die Faktoren in aufsteigender Reihenfolge auf). Um den Fundamentalsatz der Arithmetik zu beweisen, bleibt es zu zeigen, dass diese Primfaktorzerlegung eindeutig ist. Dafür benötigen wir zwei grundlegende Lemmata.

Lemma von Bézout: Der größte gemeinsame Teiler von zwei positiven ganzen Zahlen $a$ und $b$ ist die kleinste positive ganze Zahl der Form $ax + by$, wobei $x$ und $y$ ganze Zahlen (aber nicht unbedingt positive) sind.

Beweis: Sei $A$ die Menge aller ganzen Zahlen der Form $ax + by$, wobei $x$ und $y$ ganze Zahlen (möglicherweise $0$ oder negativ) sind, und sei $d$ die kleinste positive Zahl in der Menge $A$. Auf geschickte Weise ist hier tatsächlich das Auswahlaxiom versteckt. Nach Definition von $A$ gibt es ganze Zahlen $u$ und $v$, sodass $d = au + bv$. Sei $q$ der Quotient und $r$ der Rest der Division von $a$ durch $d$, sodass $a = qd + r$ mit $0 \leq r < d$. Dann gilt $r = a − qd = a − q(au + bv) = a(1 − qu) + b(−qv)$, was zeigt, dass $r$ ein Element von $A$ ist. Da $d$ jedoch das kleinste positive Element von $A$ war, muss $r$ gleich $0$ sein. Daher teilt $d|a$. Ein ähnliches Argument zeigt, dass $d|b$ teilt, sodass $d$ ein gemeinsamer Teiler von $a$ und $b$ ist. Nehmen wir nun an, dass $e$ ebenfalls ein gemeinsamer Teiler von $a$ und $b$ ist. Dann gibt es ganze Quotienten $q_1$ und $q_2$, sodass $a = q_1e und $b = q_2e$. Aber dann gilt $d = au + bv = q_1eu + q_2ev = (q_1u + q_2v)e$, und da $d$ und $e$ positiv sind, muss $(q_1u + q_2v) \geq 1$ sein, und daher $d \geq e$. Es folgt, dass $d$ der größte gemeinsame Teiler von $a$ und $b$ ist.

Korollar: Der obige Beweis zeigt, dass jeder gemeinsame Teiler von zwei positiven ganzen Zahlen $a$ und $b$ tatsächlich auch ein Teiler des größten gemeinsamen Teilers von $a$ und $b$ ist.

Euklids Lemma: Sei $p$ eine Primzahl und $a_1, a_2, \ldots, a_k$ positive ganze Zahlen ($k \geq 2$). Wenn $p$ keine der Zahlen $a_1, a_2, \ldots, a_k$ teilt, dann teilt $p$ auch nicht das Produkt $a_1 \cdot a_2 \cdots a_k$.

Beweis: Angenommen, $p$ teilt keine der Zahlen $a_1, a_2, \ldots, a_k$, aber $p$ teilt das Produkt $a_1a_2 \cdots a_k$. Da $p|a_1a_2 \cdots a_k$ teilt, können wir $a_1 a_2 \cdots a_k = pm$ für eine positive ganze Zahl $m$ schreiben. Betrachten wir nun die Primfaktorzerlegung jeder Zahl $a_i: a_i = p^{x_i} \cdot b_i$, wobei $b_i$ eine positive ganze Zahl und $x_i$ eine nicht-negative ganze Zahl ist. Setzen wir dies in das Produkt $a_1a_2 \cdots a_k$ ein, erhalten wir: $a_1a_2 \cdots a_k = (p^{x_1} \cdot b_1)(p^{x_2} \cdot b_2) \cdots (p^{x_k} \cdot b_k) = p^{(x_1+x_2+…+x_k)} \cdot (b_1b_2 \cdots b_k)$ Da $p \vert a_1a_2 \cdots a_k$ teilt, muss es auch $p^{(x1+x2+…+xk)} \cdot (b_1b_2 \cdots b_k)$ teilen. Da $p$ jedoch eine Primzahl ist und keine der Zahlen $a_1, a_2, \ldots, a_k$ teilt, kann es keines der Faktoren $p^{x_i}$ teilen. Daher muss $p \vert (b_1b_2 \cdots b_k)$ teilen. Aber das widerspricht unserer ursprünglichen Annahme, dass $p$ keine der Zahlen $a_1, a_2, \ldots, a_k$ teilt. Daher ist unsere Annahme, dass $p$ das Produkt $a_1a_2 \cdots a_k$ teilt, falsch. Daher, wenn $p$ keine der Zahlen $a1, a_2, \ldots, a_k$ teilt, dann teilt $p$ auch nicht das Produkt $a_1a_2 \cdots a_k$. $\blacksquare$

Beweis von Euklids Satz: Die obigen Lemmata besagen, dass jede Zahl größer als $1$ mindestens eine Primfaktorisierung hat, aber wir müssen immer noch beweisen, dass diese Primfaktorisierung eindeutig ist. Um dies zu beweisen, nehmen wir an, dass es Zahlen größer als $1$ gibt, die mehr als eine Primfaktorisierung haben. Dann gibt es eine kleinste solche Zahl. Nennen wir sie $n$ und lassen Sie $p_1p_2 \cdots p_k$ und $q_1q_2 \cdots q_l$ zwei verschiedene Primfaktorisierungen von $n$ sein. Offensichtlich, wenn $k = 1$ oder $l = 1$, dann wäre die Zahl $n$ selbst eine Primzahl und die beiden Primfaktorisierungen müssten gleich sein, also muss es der Fall sein, dass $k \geq 2$ und $l \geq 2$. Lassen Sie nun $r$ das größte der beiden Primzahlen $p_k$ und $q_l$ sein. Unabhängig davon, welche der beiden größer ist, folgt aus den beiden Primfaktorisierungen von $n$, dass die Zahl $n$ durch $r$ teilbar ist. Insbesondere ist das Produkt $p_1p_2 \dots p_k$ durch $r$ teilbar, also muss nach dem Lemma von Euklid mindestens einer der Faktoren $p_1, p_2, \ldots , p_k$ durch $r$ teilbar sein. Da $p1 \leq p2 \leq \cdots \leq p_k \leq r$ gilt, folgt daraus, dass $r = p_k$ ist. Mit einem ähnlichen Argument gilt auch $r = q_l$. Aber das ist unmöglich, denn dann wäre die Zahl $\frac{n}{r}$ eine ganze Zahl kleiner als $n$ mit zwei verschiedenen Primfaktorisierungen $p_1p_2 \cdots p_{k−1}$ und $q_1q_2 \ldots q_{l−1}$. $\blacksquare$