next up previous contents index
Nächste Seite: Die Eulersche -Funktion und Aufwärts: Die Ringe und Vorherige Seite: Die Ringe und   Inhalt   Index

Der chinesische Restsatz

Der chinesische Restsatz ist einer der anwendungsreichsten Sätze der elementaren Zahlentheorie. Man benutzt ihn z. B. zum schnellen Rechnen im Ring $ \mathbb{Z}_n$ . Wir geben zunächst eine algebraische Formulierung dieses Satzes an.





Satz 4.59 (Chinesischer Restsatz)   Sei $ n = n_1 n_2 \cdots n_r$ das Produkt paarweise teilerfremder natürlicher Zahlen $ n_1, \ldots ,
n_r$ , alle $ n_i \geq 2$ . Dann ist $ \mathbb{Z}_n$ isomorph zum direkten Produkt $ \mathbb{Z}_{n_1} \times
\cdots \times \mathbb{Z}_{n_r}$ . Ein Isomorphismus wird durch $ \varphi: x$    mod $ n \mapsto (x \,$   mod $ n_1, \ldots , x \,$   mod $ n_r)$ gegeben.



Beweis: Wegen $ n_j \vert n$ ist $ n \mathbb{Z}\subseteq n_j\mathbb{Z}$ für alle $ j$ . Also ist $ x + n \mathbb{Z}\subseteq x + n_j \mathbb{Z}$ . Damit erhalten wir einen wohldefinierten Homomorphismus von $ \mathbb{Z}/n \mathbb{Z}$ in $ \mathbb{Z}/n_1 \mathbb{Z}
\times \cdots \times \mathbb{Z}/n_r \mathbb{Z}$ gegeben durch $ x + n\mathbb{Z}\mapsto
(x + n_1\mathbb{Z}, \ldots, x + n_r\mathbb{Z})$ . Satz 4.56 c) ergibt, dass dann auch die Zuordnung $ \varphi$ wohldefiniert und ein Homomorphismus ist. Ist $ x$    mod $ n \in \ker(\varphi)$ , so folgt $ n_j \vert x$ für $ j = 1, \ldots, r$ und daher wegen der paarweisen Teilerfremdheit der $ n_j$ auch $ m \vert x$ nach Korollar 3.12 b), d. h. $ x$    mod $ n = 0$ . Also ist $ \varphi$ injektiv. Wegen $ \vert\mathbb{Z}_n\vert =
\vert\mathbb{Z}_{n_1} \times \cdots \times \mathbb{Z}_{n_r}\vert$ ist $ \varphi$ auch surjektiv (Satz 2.14), also ein Isomorphismus.$ \Box$

Worin liegt die Bedeutung des chinesischen Restsatzes für das Rechnen mit dem Computer? Ist $ n$ sehr groß, so dass eigens eine Langzahlarithmetik benutzt werden müsste, so ist das Rechnen im Produktring $ \mathbb{Z}_{n_1}
\times \cdots \times \mathbb{Z}_{n_r}$ wesentlich schneller, wenn die $ n_j$ schon Maschinenzahlen sind.

In der Sprache der Zahlentheorie lautet Satz 4.59 folgendermaßen:





Korollar 4.60   Seien $ n_1, \ldots, n_r$ paarweise teilerfremde natürliche Zahlen und $ a_1, \ldots, a_r$ beliebige ganze Zahlen. Dann gibt es genau eine natürliche Zahl $ x$ mit $ 0 \leq x \leq n_1 \cdots n_r - 1$ , die das folgende Kongruenzsystem löst:
$\displaystyle x$ $\displaystyle \equiv$ $\displaystyle a_1\pmod{n_1}$  
    $\displaystyle \vdots$  
$\displaystyle x$ $\displaystyle \equiv$ $\displaystyle a_r\pmod{n_r}$  




Beweis: Wir können ohne Beschränkung der Allgemeinheit $ n_i \geq 2$ für $ i
= 1, \ldots, r$ annehmen. Die Existenz von $ x$ entspricht der Surjektivität der Abbildung $ \varphi$ aus Satz 4.59, die Eindeutigkeit im Bereich $ 0 \leq x
\leq n_1 \ldots n_r - 1$ der Injektivität.$ \Box$

Konstruktive Lösung des Gleichungssystems in Korollar 4.60. Der Beweis von Satz 4.59 gibt keinen Hinweis darauf, wie man die Lösung $ x$ in 4.60 tatsächlich berechnen kann. Wir wollen dies nachholen. Die Idee ist, zunächst für jedes $ i$ eine Lösung für den Fall $ a_i = 1$ und $ a_j = 0$ für $ j \neq i$ zu bestimmen. (In der Formulierung von Satz 4.59 bedeutet dies, Urbilder der Elemente $ (0, \ldots,
0,\underbrace{1}_{i\mbox {\footnotesize --te Stelle}}, 0, \ldots,
0)$ zu bestimmen.) Aus diesen speziellen Lösungen lassen sich dann leicht die Lösungen für beliebige $ a_1, \ldots, a_r$ zusammenbauen.
Sei also $ i \in \{1, \ldots, r\}$ und $ N_i = \prod_{j \neq i} n_j$ . Dann sind $ N_i$ und $ n_i$ teilerfremd. Damit gibt es nach Korollar 3.13 ein $ t_i$ mit $ t_iN_i \equiv 1\pmod{n_i}$ . Es ist klar, dass $ t_iN_i \equiv 0\pmod{n_j}$ für alle $ j \neq i$ . Sind nun $ a_1, \ldots, a_r$ beliebige ganze Zahlen, so setzt man $ y = \sum_{i = 1}^r a_i t_i N_i$ und es folgt sofort, dass $ y \equiv a_i\pmod{n_i}$ für $ i = 1, \ldots, r$ . $ x = y \bmod n$ ist dann die gesuchte Lösung.


next up previous contents index
Nächste Seite: Die Eulersche -Funktion und Aufwärts: Die Ringe und Vorherige Seite: Die Ringe und   Inhalt   Index
friedric 2004-08-18