Kurs:Elemente der Algebra (Osnabrück 2015)/Vorlesung 16

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

Dies folgt unmittelbar aus Satz 15.7.

$\Box$

Beweisvariante

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. Es sei ${}x$ eine natürliche Zahl, die im Produktring (rechts) zu ${}0$ wird, also modulo ${}p_{i}^{r_{i}}$ den Rest ${}0$ 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. in der Primfaktorzerlegung von ${}x$ muss ${}p_{i}$ zumindest mit dem Exponenten ${}r_{i}$ vorkommen. Also muss ${}x$ nach Lemma 9.9 ein Vielfaches des Produktes sein, also ein Vielfaches von ${}n$. Damit ist ${}x=0$ in ${}\mathbb {Z} /(n)$ und die Abbildung ist injektiv.

Unter den Basislösungen zu einer simultanen Kongruenz versteht man die kleinsten natürlichen Zahlen, die modulo den vorgegebenen Zahlen ein Restetupel ergeben, das an genau einer Stelle den Wert ${}1$ und sonst überall den Wert ${}0$ besitzt. Aus diesen Basislösungen kann man die Lösungen zu sämtlichen simultanen Kongruenzen berechnen.

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

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.6.

$\Box$

Die Eulersche ${}\varphi$-Funktion

Satz

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

Dies folgt aus Lemma 14.9.

$\Box$

Beweisvariante

Sind ${}a$ und ${}n$ teilerfremd, so gibt es nach Satz 8.5 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.

Leonhard Euler (1707-1783)

Definition

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  

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

Für eine Primzahl ${}p$ ist ${}{\varphi (p)}=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^{\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

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

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 16.3 und die zweite aus Lemma 16.8.

$\Box$

<< | Kurs:Elemente der Algebra (Osnabrück 2015) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)