Kurs:Elemente der Algebra (Osnabrück 2024-2025)/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$

Divisionsalgorithmus und multiplikative Ordnung

Es ist

${}{\frac {1}{7}}=0,{\overline {142857}}\,,$

die Periodenlänge ist also ${}6$. Zugleich besteht die Einheitengruppe von ${}\mathbb {Z} /(7)$ aus ${}6$ Elementen. Wir bringen hier generell den Divisionsalgorithmus (das schrifltiche dividieren) für die Berechnung der Dezimalentwicklung von ${}1$ durch ${}n$ mit dem Restklassenring ${}\mathbb {Z} /(n)$ in Verbindung. Insbesondere ergibt sich ein Zusammenhang zwischen der Periodenlänge der Dezimalentwicklung und der multiplikativen Ordnung der ${}10$ in ${}\mathbb {Z} /(n)$, falls ${}n$ teilerfrem zu ${}10$, also ${}10$ eine Einheit in ${}\mathbb {Z} /(n)$ ist. Der Divisionsalgorithmus zu ${}1$ durch ${}n$ funktioniert nach dem Schema (siehe Verfahren 28.2 (Grundkurs Mathematik (Osnabrück 2022-2023)) und Lemma 28.3 (Grundkurs Mathematik (Osnabrück 2022-2023)))

${}1=z_{0}\cdot n+r_{0}=0+1\,,$

${}10\cdot r_{0}=z_{-1}\cdot n+r_{-1}\,,$

${}10\cdot r_{-1}=z_{-2}\cdot n+r_{-2}\,,$

${}10\cdot r_{-2}=z_{-3}\cdot n+r_{-3}\,,...$

Es wird sukzessive Divisionen mit Rest durchgeführt, die ${}z_{-i}$ bezeichnen die ${}i$-te Nachkommaziffer des Bruches ${}{\frac {1}{n}}$ und der Rest ${}r_{-i}$ wird mit ${}10$ multipliziert, um die nächste Nachkommaziffer und den nächsen Rest zu erhalten. Wenn sich ein Rest wiederholt (und das muss passieren, da es ja nur endlich viele Reste gibt), so wiederholen sich ab dieser Stelle auch die Ziffern (die Ziffern können sich wiederholen, ohne dass daran schon das periodische Verhalten ablesbar ist) und man erhält eine Periodizität.

Satz

Es sei ${}n$ eine positive natürliche Zahl mit der Faktorzerlegung

${}n=2^{r}\cdot 5^{s}\cdot d\,,$

wobei ${}d$ zu ${}n$ teilerfremd sei.

Dann ist die Periodenlänge der Dezimalentwicklung von ${}{\frac {1}{n}}$ gleich der multiplikativen Ordnung von ${}10$ in ${}\mathbb {Z} /(d)$.

Beweis

Die Fälle ${}r,s=0$ oder ${}d=1$ sind erlaubt. Die Periodenlänge einer abbrechenden Dezimalentwicklung verstehen wir als ${}1$ (die ${}0$ wiederholt sich). Da die ${}10$ teilerfremd zu ${}d$ ist, ist ${}10$ in ${}\mathbb {Z} /(d)$ eine Einheit und besitzt daher eine multiplikative Ordnung. Der Divisionsalgorithmus berechnet sukzessive die Reste von ${}10^{i}$ in ${}\mathbb {Z} /(n)$, da ja der vorhergehende Rest mit ${}10$ multipliziert wird. Periode tritt ein, wenn sich Reste erstmalig wiederholen, wenn also ${}10^{i}=10^{j}$ in ${}\mathbb {Z} /(n)$ mit ${}i<j$ ist und ${}i,j$ minimal mit dieser Eigenschaft sind. Der chinesische Restsatz liefert die Isomorphie

${}\mathbb {Z} /(n)=\mathbb {Z} /(2^{r})\times \mathbb {Z} /(5^{s})\times \mathbb {Z} /(d)\,,$

und die Bedingung ${}10^{i}=10^{j}$ muss in den drei Komponenten gelten. In den ersten beiden Komponenten ist ${}10$ nilpotent, da ja ${}10^{r}$ ein Vielfaches von ${}2^{r}$ und ${}10^{s}$ ein Vielfaches von ${}5^{s}$ ist. Diese Komponenten sind also für die Periodenlänge unerheblich (allerdings spielen sie eine Rolle für die Frage, wann frühestens die Periodizität anfängt). In der dritten Komponente ist ${}10$ eine Einheit, also ein Element der Einheitengruppe ${}{\left(\mathbb {Z} /(d)\right)}^{\times }$. Nach Lemma 1.11 tritt die erste Wiederholung ein, wenn erstmalig ${}10^{j}=10^{0}=1$ gilt, also bei der multiplikativen Ordnung von ${}10$.

$\Box$

Dass die Dezimalentwicklung von ${}{\frac {1}{7}}$ die Periode ${}6$ besitzt hängt unmittelbar damit zusammen, dass ${}10=3$ in ${}\mathbb {Z} /(7)$ ein Erzeuger der Einheitengruppe ist. Es ist

${}{\frac {1}{11}}=0,{\overline {09}}\,,$

die Periodenlänge ${}2$ ist die multiplikative Ordnung von ${}10=-1$ in ${}\mathbb {Z} /(11)$. Die Berechnung der multiplikativen Ordnung von ${}10$ in ${}\mathbb {Z} /(d)$ vereinfacht sich, wenn man für ${}d$ die Faktorzerlegung in zueinander teilerfremde Faktoren kennt.

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