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, so dass 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:  Bei ${}n=2$ ist die Aussage klar. Im Allgemeinen seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir

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

Insbesondere teilt die Primzahl ${}p_{1}$ dann das Produkt rechts, und damit nach dem Lemma von Euklid einen der Faktoren. 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. Da ${}\mathbb {Z}$ nullteilerfrei ist, kann man beidseitig durch ${}p_{1}=q_{1}$ dividieren und erhält die Gleichung

${}n^{\prime }=p_{2}{\cdots }p_{r}=q_{2}{\cdots }q_{s}\,.$

Da ${}n'<n$ ist, können wir die Induktionsvoraussetzung der Eindeutigkeit auf ${}n'$ anwenden. 

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

${}n=\prod _{p}p^{\nu _{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

${}{\nu _{p}(n)}\geq {\nu _{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^{{\nu _{p}(n)}-{\nu _{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^{\nu _{p}(n)}$ und ${}m=\prod _{p}p^{\nu _{p}(m)}$.

Dann ist

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

und

${}\operatorname {ggT} (n,m)=\prod _{p}p^{\min {\left({\nu _{p}(n)},{\nu _{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, so dass also

${}ar-1=sn\,$

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

$\Box$

Leonhard Euler (1707-1783)

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

$0,p,2p,3p,\ldots ,(p^{r-1}-1)p$

Vielfache von ${}p$. Das sind ${}p^{r-1}$ Stück, und daher gibt es

${}p^{r}-p^{r-1}=p^{r-1}(p-1)\,$

Einheiten in ${}\mathbb {Z} /(p^{r})$. Also ist ${}{\varphi (p^{r})}=p^{r-1}(p-1)$.

$\Box$

Korollar Korollar 15.6 ändern

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

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

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

Dann ist

${}{\varphi (n)}={\varphi (p_{1}^{r_{1}})}{\cdots }{\varphi (p_{k}^{r_{k}})}=(p_{1}-1)p_{1}^{r_{1}-1}{\cdots }(p_{k}-1)p_{k}^{r_{k}-1}\,.$

Beweis

Die erste Gleichung folgt aus Korollar 15.10 und die zweite aus Lemma 15.15.

$\Box$

<< | Kurs:Einführung in die Algebra (Osnabrück 2009) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)