Kurs:Einführung in die Algebra (Osnabrück 2009)/Vorlesung 15

Der Hauptsatz der elementaren Zahlentheorie

Wir beweisen nun, dass sich jede natürliche Zahl in eindeutiger Weise als Produkt von Primzahlen darstellen lässt.

Satz

Es sei $p$ eine Primzahl und $p$ teile ein Produkt $a b$ von natürlichen Zahlen $a, b \in ℕ$ .

Dann teilt $p$ einen der Faktoren.

Beweis

Die Voraussetzung bedeutet, dass

\overline{a} \overline{b} = \overline{0} = 0

in $ℤ / (p)$ ist. Da $p$ eine Primzahl ist, ist dieser Restklassenring nach Satz 14.13 ein Körper, sodass ein Faktor null sein muss. Sagen wir $\overline{a} = 0$ . Dies bedeutet aber zurückübersetzt nach $ℤ$ , dass $a$ ein Vielfaches von $p$ ist.

◻

Satz

Jede natürliche Zahl $n \in ℕ$ , $n \geq 2$ ,

besitzt eine eindeutige Zerlegung in Primfaktoren.

D.h. es gibt eine Darstellung

n = p_{1} \dots p_{r}

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

Beweis

Wir beweisen die Existenz und die Eindeutigkeit jeweils durch Induktion. Für $n = 2$ liegt eine Primzahl vor. Bei $n \geq 3$ ist entweder $n$ eine Primzahl, und diese bildet die Primfaktorzerlegung, oder aber $n$ ist keine Primzahl. In diesem Fall gibt es eine nichttriviale Zerlegung $n = a b$ mit kleineren Zahlen $a, b < n$ . Für diese Zahlen gibt es nach der Induktionsvoraussetzung eine Zerlegung in Primfaktoren, und diese setzen sich zu einer Primfaktorzerlegung für $n$ zusammen. Zur Eindeutigkeit: Für $n = 2$ liegt eine Primzahl vor und die Aussage ist klar. Es sei nun $n \geq 3$ und seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir

n = p_{1} \dots p_{r} = q_{1} \dots 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 dem Lemma von Euklid 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} \dots p_{r} = q_{2} \dots 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.

◻

Zu einer Primzahl $p$ und einer positiven ganzen Zahl $n$ ist der Exponent, also die Vielfachheit, mit der $p$ als Primfaktor in $n$ auftritt, eindeutich festgelegt. Dieser Exponent wird mit $ν_{p} (n)$ bezeichnet. Die eindeutige Primfaktorzerlegung kann man auch als

n = \prod_{p} p^{ν_{p} (n)}

schreiben, wobei das Produkt in Wirklichkeit endlich ist, da in der Primfaktorzerlegung nur endlich viele Primfaktoren mit einem positiven Exponenten vorkommen.

Lemma

Es seien $n$ und $k$ positive natürliche Zahlen. Dann wird $n$ von $k$ genau dann geteilt,

wenn für jede Primzahl $p$ die Beziehung

$ν_{p} (n) \geq ν_{p} (k)$

gilt.

Beweis

$(1) \Rightarrow (2)$ . Aus der Beziehung $n = k t$ folgt in Verbindung mit der eindeutigen Primfaktorzerlegung, dass die Primfaktoren von $k$ mit mindestens ihrer Vielfachheit auch in $n$ vorkommen müssen.
$(2) \Rightarrow (1)$ . Wenn die Exponentenbedingung erfüllt ist, so ist $t = \prod_{p} p^{ν_{p} (n) - ν_{p} (k)}$ eine natürliche Zahl mit $n = k t$ .

◻

Korollar

Es seien $n$ und $m$ positive natürliche Zahlen mit den Primfaktorzerlegungen $n = \prod_{p} p^{ν_{p} (n)}$ und $m = \prod_{p} p^{ν_{p} (m)}$ .

Dann ist

$kgV (n, m) = \prod_{p} p^{max (ν_{p} (n), ν_{p} (m))}$

und

$ggT (n, m) = \prod_{p} p^{min (ν_{p} (n), ν_{p} (m))} .$

Beweis

Dies folgt direkt aus Lemma 15.3.

◻

Produktringe

Um die Restklassenringe von $ℤ$ besser verstehen zu können, insbesondere dann, wenn man $n$ als Produkt von kleineren Zahlen schreiben kann - z.B., wenn die Primfaktorzerlegung bekannt ist -, braucht man den Begriff des Produktringes.

Definition

Es seien $R_{1}, \dots, R_{n}$ kommutative Ringe. Dann heißt das Produkt

R_{1} \times \dots \times R_{n},

versehen mit komponentenweiser Addition und Multiplikation, der Produktring der $R_{i}$ , $i = 1, \dots, n$ .

Eng verwandt mit dem Begriff des Produktringes ist das Konzept der idempotenten Elemente.

Definition

Ein Element $e$ eines kommutativen Ringes heißt idempotent, wenn $e^{2} = e$ gilt.

Die Elemente $0$ und $1$ sind trivialerweise idempotent, man nennt sie die trivialen idempotenten Elemente. In einem Produktring sind auch diejenigen Elemente, die in allen Komponenten nur den Wert $0$ oder $1$ besitzen, idempotent, also bspw. $(1, 0)$ . In einem Integritätsbereich gibt es nur die beiden trivialen idempotenten Elemente: Ein idempotentes Element $e$ besitzt die Eigenschaft

e (1 - e) = e - e^{2} = e - e = 0 .

Im nullteilerfreien Fall folgt daraus $e = 1$ oder $e = 0$ .

Lemma

Es sei $R = R_{1} \times \dots \times R_{n}$ ein Produkt aus kommutativen Ringen.

Dann gilt für die Einheitengruppe von $R$ die Beziehung

$R^{\times} = R_{1}^{\times} \times \dots \times R_{n}^{\times} .$

Beweis

Dies ist klar, da ein Element genau dann eine Einheit ist, wenn es in jeder Komponente eine Einheit ist.

◻

Der Chinesische Restsatz für $ℤ$

Satz

Es sei $n$ eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung

n = p_{1}^{r_{1}} \cdot p_{2}^{r_{2}} \dots p_{k}^{r_{k}}

(die $p_{i}$ seien also verschieden und $r_{i} \geq 1$ ).

Dann induzieren die kanonischen Ringhomomorphismen $ℤ / (n) \to ℤ / (p_{i}^{r_{i}})$ einen Ringisomorphismus

$ℤ / (n) ≅ ℤ / (p_{1}^{r_{1}}) \times ℤ / (p_{2}^{r_{2}}) \times \dots \times ℤ / (p_{k}^{r_{k}}) .$

Zu gegebenen ganzen Zahlen $(a_{1}, a_{2}, \dots, a_{k})$ gibt es also genau eine natürliche Zahl $a < n$ , die die simultanen Kongruenzen

a = a_{1} mod p_{1}^{r_{1}}, a = a_{2} mod p_{2}^{r_{2}}, \dots, a = a_{k} mod p_{k}^{r_{k}}

löst.

Beweis

Da die Ringe links und rechts beide endlich sind und die gleiche Anzahl von Elementen haben, nämlich

n

, genügt es, die Injektivität zu zeigen. Sei

x

eine natürliche Zahl, die im Produktring (rechts) zu null wird, also modulo

p_{i}^{r_{i}}

den Rest null hat für alle

i = 1, 2, \dots, k

. Dann ist

x

ein Vielfaches von

p_{i}^{r_{i}}

für alle

i = 1, 2, \dots, k

, d.h., es ist ein gemeinsames Vielfaches dieser Potenzen. Daraus folgt aufgrund von

Lemma 4.8,

dass

x

ein Vielfaches des Produktes sein muss, also ein Vielfaches von

n

. Damit ist

x = 0

in

ℤ / (n)

und die Abbildung ist injektiv.

◻

Beispiel

Aufgabe

a) Bestimme für die Zahlen $3$ , $5$ und $7$ modulare Basislösungen, finde also die kleinsten positiven Zahlen, die in

ℤ / (3) \times ℤ / (5) \times ℤ / (7)

die Restetupel $(1, 0, 0), (0, 1, 0)$ und $(0, 0, 1)$ repräsentieren.

b) Finde mit den Basislösungen die kleinste positive Lösung $x$ der simultanen Kongruenzen

x = 2 mod 3, x = 4 mod 5 und x = 3 mod 7.

Lösung

a) $(1, 0, 0)$ : Alle Vielfachen von $5 \cdot 7 = 35$ haben modulo $5$ und modulo $7$ den Rest $0$ . Unter diesen Vielfachen muss also die Lösung liegen. $35$ hat modulo $3$ den Rest $2$ , somit hat $70$ modulo $3$ den Rest $1$ . Also repräsentiert $70$ das Restetupel $(1, 0, 0)$ .

$(0, 1, 0)$ : Hier betrachtet man die Vielfachen von $21$ , und $21$ hat modulo $5$ den Rest $1$ . Also repräsentiert $21$ das Restetupel $(0, 1, 0)$ .

$(0, 0, 1)$ : Hier betrachtet man die Vielfachen von $15$ , und $15$ hat modulo $7$ den Rest $1$ . Also repräsentiert $15$ das Restetupel $(0, 0, 1)$ .

b) Man schreibt (in $ℤ / (3) \times ℤ / (5) \times ℤ / (7)$ )

(2, 4, 3) = 2 (1, 0, 0) + 4 (0, 1, 0) + 3 (0, 0, 1) .

Die Lösung ist dann

2 \cdot 70 + 4 \cdot 21 + 3 \cdot 15 = 140 + 84 + 45 = 269 .

Die minimale Lösung ist dann $269 - 2 \cdot 105 = 59$ .

Korollar

Es sei $n$ eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung $n = p_{1}^{r_{1}} \cdot p_{2}^{r_{2}} \dots p_{k}^{r_{k}}$ (die $p_{i}$ seien also verschieden und $r_{i} \geq 1$ ).

Dann gibt es einen kanonischen Gruppenisomorphismus

${(ℤ / (n))}^{\times} ≅ {(ℤ / (p_{1}^{r_{1}}))}^{\times} \times \dots \times {(ℤ / (p_{k}^{r_{k}}))}^{\times} .$

Insbesondere ist eine Zahl $a$ genau dann eine Einheit modulo $n$ , wenn sie eine Einheit modulo $p_{i}^{r_{i}}$ ist für $i = 1, \dots, k$ .

Beweis

Dies folgt aus dem chinesischen Restsatz und Lemma 15.7.

◻

Die Eulersche $φ$ -Funktion

Satz

Genau dann ist $a \in ℤ$ eine Einheit modulo $n$ (d.h. $a$ repräsentiert eine Einheit in $ℤ / (n)$ ), wenn $a$ und $n$ teilerfremd sind.

Beweis

Sind $a$ und $n$ teilerfremd, so gibt es nach Fakt ***** eine Darstellung der $1$ , es gibt also ganze Zahlen $r, s$ mit

r a + s n = 1 .

Betrachtet man diese Gleichung modulo $n$ , so ergibt sich $r a = 1$ in $ℤ / (n)$ . Damit ist $a$ eine Einheit mit dem inversen Element $a^{- 1} = r$ .

Ist umgekehrt $a$ eine Einheit in $ℤ / (n)$ , so gibt es ein $r \in ℤ / (n)$ mit $a r = 1$ in $ℤ / (n)$ . Das bedeutet aber, dass $a r - 1$ ein Vielfaches von $n$ ist, sodass also

a r - 1 = s n

gilt. Dann ist aber wieder $a r - s n = 1$ und $a$ und $n$ sind teilerfremd.

◻

Definition

Zu einer natürlichen Zahl $n$ bezeichnet $φ (n)$ die Anzahl der Elemente von $(ℤ / (n))^{\times}$ . Man nennt $φ (n)$ die Eulersche Funktion.

Bemerkung

Die Eulersche Funktion $φ (n)$ gibt also für $n \geq 1$ nach Satz 15.11 an, wie viele Zahlen $r$ , $0 \leq r < n$ , zu $n$ teilerfremd sind.

Für eine Primzahl ist $φ (n) = p - 1$ . Eine Verallgemeinerung des kleinen Fermat ist der folgende Satz von Euler.

Satz

Es sei $n$ eine natürliche Zahl.

Dann gilt für jede zu $n$ teilerfremde Zahl $a$ die Beziehung

$a^{φ (n)} = 1 mod n .$

Beweis

Das Element $a$ gehört zur Einheitengruppe ${(ℤ / (n))}^{\times}$ , die $φ (n)$ Elemente besitzt. Nach dem Satz von Lagrange ist aber die Gruppenordnung ein Vielfaches der Ordnung des Elementes.

◻

Wir geben abschließend Formeln an, wie man die Eulersche $φ$ -Funktion berechnet, wenn die Primfaktorzerlegung bekannt ist.

Lemma

Es sei $p$ eine Primzahl und $p^{r}$ eine Potenz davon.

Dann ist

$φ (p^{r}) = p^{r - 1} (p - 1) .$

Beweis

Eine Zahl $a$ ist genau dann teilerfremd zu einer Primzahlpotenz $p^{r}$ , wenn sie teilerfremd zu $p$ selbst ist, und dies ist genau dann der Fall, wenn sie kein Vielfaches von $p$ ist. Unter den natürlichen Zahlen $< p^{r}$ sind genau die Zahlen