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

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 Referenznummer erstellen

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

Die Voraussetzung bedeutet, dass

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

in ${}\mathbb {Z} /(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 ${}\mathbb {Z}$ , dass ${}a$ ein Vielfaches von ${}p$ ist.

\Box

Satz Referenznummer erstellen

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

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=ab$ 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}{\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 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}{\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

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 ${}{\exp _{p}(n)}$ bezeichnet. Die eindeutige Primfaktorzerlegung kann man auch als

{}n=\prod _{p}p^{\exp _{p}(n)}\,

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

Lemma Lemma 15.3 ändern

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

${}{\exp _{p}(n)}\geq {\exp _{p}(k)}\,$

gilt.

Beweis

${}(1)\Rightarrow (2)$ . Aus der Beziehung ${}n=kt$ 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^{{\exp _{p}(n)}-{\exp _{p}(k)}}$ eine natürliche Zahl mit ${}n=kt$ .

\Box

Korollar Referenznummer erstellen

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

Dann ist

${}\operatorname {kgV} (n,m)=\prod _{p}p^{\max {\left({\exp _{p}(n)},{\exp _{p}(m)}\right)}}\,$

und

{}\operatorname {ggT} (n,m)=\prod _{p}p^{\min {\left({\exp _{p}(n)},{\exp _{p}(m)}\right)}}\,.

Beweis

Dies folgt direkt aus Lemma 15.3.

\Box

Produktringe

Um die Restklassenringe von ${}\mathbb {Z}$ 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 Referenznummer erstellen

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

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

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

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

Definition Referenznummer erstellen

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 Lemma 15.7 ändern

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

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

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

Beweis

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

\Box

Der Chinesische Restsatz für ${}\mathbb {Z}$

Satz

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

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

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

Dann induzieren die kanonischen Ringhomomorphismen ${}\mathbb {Z} /(n)\rightarrow \mathbb {Z} /(p_{i}^{r_{i}})$ einen Ringisomorphismus

${}\mathbb {Z} /(n)\cong \mathbb {Z} /(p_{1}^{r_{1}})\times \mathbb {Z} /(p_{2}^{r_{2}})\times \cdots \times \mathbb {Z} /(p_{k}^{r_{k}})\,.$

Zu gegebenen ganzen Zahlen ${}(a_{1},a_{2},\ldots ,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}},\,\ldots ,\,\,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,\ldots ,k

. Dann ist

{}x

ein Vielfaches von

{}p_{i}^{r_{i}}

für alle

{}i=1,2,\ldots ,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

{}\mathbb {Z} /(n)

und die Abbildung ist injektiv.

\Box

Beispiel

Aufgabe

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

\mathbb {Z} /(3)\times \mathbb {Z} /(5)\times \mathbb {Z} /(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{\text{ 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 $\mathbb {Z} /(3)\times \mathbb {Z} /(5)\times \mathbb {Z} /(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 Korollar 15.10 ändern

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

Dann gibt es einen kanonischen Gruppenisomorphismus

${}{\left(\mathbb {Z} /(n)\right)}^{\times }\cong {\left(\mathbb {Z} /(p_{1}^{r_{1}})\right)}^{\times }\times \cdots \times {\left(\mathbb {Z} /(p_{k}^{r_{k}})\right)}^{\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,\ldots ,k$ .

Beweis

Dies folgt aus dem chinesischen Restsatz und Lemma 15.7.

\Box

Die Eulersche ${}\varphi$ -Funktion

Satz Satz 15.11 ändern

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

Beweis

Sind ${}a$ und ${}n$ teilerfremd, so gibt es nach Satz 4.1 eine Darstellung der ${}1$ , es gibt also ganze Zahlen ${}r,s$ mit

{}ra+sn=1\,.

Betrachtet man diese Gleichung modulo ${}n$ , so ergibt sich ${}ra=1$ in ${}\mathbb {Z} /(n)$ . Damit ist ${}a$ eine Einheit mit Inversem ${}a^{-1}=r$ .

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

{}ar-1=sn\,

gilt. Dann ist aber wieder ${}ar-sn=1$ und ${}a$ und ${}n$ sind teilerfremd.

\Box

Definition Referenznummer erstellen

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

Bemerkung Referenznummer erstellen

Die Eulersche Funktion ${}\varphi (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 ${}{\varphi (n)}=p-1$ . Eine Verallgemeinerung des kleinen Fermat ist der folgende Satz von Euler.

Satz Referenznummer erstellen

Es sei ${}n$ eine natürliche Zahl.

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

${}a^{\varphi (n)}=1\!\!\!\mod n\,.$

Beweis

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

\Box

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

Lemma Lemma 15.15 ändern

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

Dann ist

${}{\varphi (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