Höhere Mathematik

Chinesischer Restsatz

Inhaltsübersicht

Dieser Artikel befasst sich mit dem chinesischen Restsatz. Darunter wird im Allgemeinen der chinesische Restsatz für allgemeine Ringe verstanden. Im Speziellen lässt sich der Satz auch für Hauptidealringe wie beispielsweise den ganzen Zahlen formulieren. Auf den chinesischen Restsatz für ganze Zahlen soll in diesem Artikel etwas genauer eingegangen werden. Mithilfe des Satzes wird zunächst aufgezeigt, wie simultane Kongruenzen in verschiedenen Fällen gelöst werden können. Anschließend wird dieses Vorgehen mit Beispielen untermauert.

Das Wichtigste rund um das Thema chinesischer Restsatz haben wir auch noch in einem kurzen Video für dich zusammengefasst. Dadurch sparst du dir Zeit und Lesearbeit und erhältst trotzdem einen guten Überblick über das Thema!

Chinesischer Restsatz für allgemeine Ringe

Der chinesische Restsatz trifft eine Aussage über die Isomorphie zwischen einem Faktorring R modulo des Schnittes koprimer Ideale a_i und dem Produkt der Faktorringe R modulo a_i . Für den Ring der ganzen Zahlen lässt sich der chinesische Restsatz anwenden, um simultane Kongruenzen zu lösen.
Doch hier soll der Satz zunächst einmal für allgemeine Ringe konkret formuliert werden:

Sei R ein Ring und seien a_1, \dots ,a_n Ideale von R mit der Eigenschaft a_i+a_j=R für alle i\neqj , also paarweise teilerfremde bzw. koprime Ideale. Dann ist die folgende Abbildung ein Isomorphismus:

f :  \left\{ \begin{array}{ll} R/(a_1\ \cap ... \cap a_n) \rightarrow R/a_1\ x...x\ R/a_n \\ r+a_1 \cap ... \cap a_n \rightarrow (r+a_1, ... ,r+ a_n)  \\ \end{array} \right.

Chinesischer Restsatz für Hauptidealringe

Für den Spezialfall, dass der betrachtete Ring R ein Hauptidealring ist, lässt sich der Satz wie folgt formulieren:

Sei R ein Hauptidealring und seien r_1, \dots ,r_n \in R paarweise teilerfremd, d.h. es gilt für alle i\neq j die Gleichung r_i R+r_j R=R . Dann ist die folgende Abbildung ein Isomorphismus:

f :  \left\{ \begin{array}{ll} R/(r_1 \cdot ... \cdot r_n) \rightarrow R/ (r_1) x ... x R/(r_n)  \\ r+r_1 \cdot ... \cdot r_n R \rightarrow (r+r_1 R, ... , r+r_nR)   \\ \end{array} \right.

Äquivalent zu der Forderung, dass für alle i \neq j gilt r_i R+r_j R=R, also dass die Ringelemente r_1,\dots , r_n\in R paarweise teilerfremd sind, ist die Tatsache, dass für alle i\neq j gilt: „ggT“ (a_i,a_j )=1.

Chinesischer Restsatz für ganze Zahlen

Umgemünzt auf den Hauptidealring der ganzen Zahlen lässt sich der chinesische Restsatz folgendermaßen formulieren:

 

ganze Zahlen, chinesischer Restsatz, Isomorphismus, paarweise Restsatz, Faktorring, modulo, Hauptring
Chinesischer Restsatz mit ganzen Zahlen

Sind die ganzen Zahlen z_1,\dots ,z_n\in \mathbb{Z} paarweise teilerfremd, so ist die folgende Abbildung ein Isomorphismus:

f :  \left\{ \begin{array}{ll} \mathbb{Z} / (z_1 \cdot ... \cdot z_n) \rightarrow \mathbb{Z} / (z_1)\ x ... x\ \mathbb{Z} /(z_n)  \\ z+z_1 \cdot ... \cdot z_n \mathbb{Z} \rightarrow (z+z_1 \mathbb{Z} , ... , z+z_n \mathbb{Z}   \\ \end{array} \right.

Der Chinesische Restsatz für ganze Zahlen wird meist in Bezug auf simultane Kongruenzen formuliert.

Simultane Kongruenzen ganzer Zahlen

Mit einer simultanen Kongruenz ganzer Zahlen ist ein System von linearen Kongruenzen gemeint:

x\equiv\ x_1\mathrm{\mathrm{\ (}mod}{\ a}_1)
x\equiv\ x_2\mathrm{\mathrm{\ (}mod}{\ a}_2)
\vdots
x\equiv\ x_n\mathrm{\mathrm{\ (}mod}{\ a}_n)

Ist diejenige Zahl x gesucht, die zu den vorgegebenen Zahlen x_1,\dots ,x_n und a_1,\dots ,a_n eine Lösung der simultanen Kongruenz ist, so trifft der chinesische Restsatz eine Aussage zu dieser Lösung:

Sind die ganzen Zahlen a_1,\dots ,a_n\in \mathbb{Z} paarweise teilerfremd, so ist das gegebene System simultaner Kongruenzen x\equiv\ x_1\mathrm{\mathrm{\ (}mod}{\ a}_1) mit i=1,\dots ,n für beliebige ganze Zahlen x_1,\dots ,x_n \in \mathbb{Z} lösbar. Eine Lösung x dieser Kongruenzen ist dann eindeutig bestimmt modulo a_1\cdot \dots\cdot a_n .
Der Beweis dieser Aussage liefert auch gleichzeitig ein Verfahren zur Bestimmung dieser Lösung.

Chinesischer Restsatz: Beweis

Zunächst einmal soll die Existenz einer Lösung x der simultanen Kongruenz gezeigt werden. Hierzu wird mit A≔a_1\cdot \dots \cdot a_n das Produkt der paarweise teilerfremden Moduln definiert. Weiter wird A_i≔\frac{A}{a_i} definiert. Aufgrund der Teilerfremdheit der Moduln a_1,\dots ,a_n\in \mathbb{Z} gilt:

"ggT"\ (A_i,a_i )=1

Das heißt, es können beispielsweise mit dem erweiterten euklidischen Algorithmus ganze Zahlen r_i und s_i gefunden werden, sodass gilt:

r_i\cdot\ a_i+s_i\cdot\ A_i=1

Es gilt demzufolge für e_i := s_i\cdot A_i:

e_i=1\mathrm{\mathrm{(}mod}{\ a}_i)
e_i=0\mathrm{\mathrm{(}mod}{\ a}_j),\ j\neq\ i

Eine Lösung der simultanen Kongruenz ist dann durch

x:=\sum_{i=1}^{n}{x_i\cdot e_i}

gegeben.
Nun soll gezeigt werden, dass diese Lösung eindeutig modulo a_1\cdot \dots \cdot a_n ist. Dazu wird zunächst angenommen, dass y eine weitere Lösung sei. Dann gilt:

y\equiv\ x_i\mathrm{\mathrm{\ (}mod}{\ a}_i)

Allerdings gilt auch weiterhin

x\equiv\ x_i\mathrm{\mathrm{\ (}mod}{\ a}_i)

Daher muss also y kongruent zu x modulo a_1 sein. Es gilt also:

y\equiv\ x\mathrm{\mathrm{\ (}mod}{\ a}_i)

Das wiederum bedeutet nichts anderes, als dass jedes a_i die Differenz zwischen y und x teilt:

a_i |(y-x)

Da die Moduln a_i paarweise teilerfremd sind, teilt auch deren Produkt A:= a_1⋅…⋅a_n die Differenz zwischen y und x :

A|(y-x)

Das heißt die weitere Lösung y der simultanen Kongruenz ist kongruent zur Lösung x modulo a_1\cdot \dots \cdot a_n:

y\equiv\ x\mathrm{\mathrm{\ (}mod\ }a_1\cdot\ldots\cdot\ a_n)

Chinesischer Restsatz: Nicht teilerfremde Moduln

Für den Fall, dass die Moduln a_i nicht teilerfremd sind, gibt es unter der Voraussetzung, dass für alle i \neq j gilt:

x_i\equiv\ x_j\left(mod\ ggT\left(a_i,a_j\right)\right)

auch eine Lösung der simultanen Kongruenz. Alle Lösungen sind dann kongruent modulo dem kleinsten gemeinsamen Vielfachen der a_i.

Eine Lösung lässt sich dann durch sukzessive Substitution von Kongruenzen lösen, bis sich eine simultane Kongruenz mit paarweise teilerfremden Moduln ergibt. Dieses lässt sich dann wie im Beweis des Restsatzes gezeigt lösen. Wie die sukzessive Substitution erfolgt, soll später an einem konkreten Beispiel gezeigt werden.

Chinesischer Restsatz Beispiel

Zunächst soll allerdings ein Beispiel durchgerechnet werden, bei dem die Moduln teilerfremd sind.

Beispiel: Chinesischer Restsatz teilerfremde Moduln

Gesucht sei eine ganze Zahl x mit der Eigenschaft:

x\equiv2\mathrm{\mathrm{\ (}mod\ }3)
x\equiv3\mathrm{\mathrm{\ (}mod\ }4)
x\equiv2\mathrm{\mathrm{\ (}mod\ }5)

Zum Finden einer Lösung wird nun die Argumentationskette des Beweises abgearbeitet. Zunächst wird das Produkt der teilerfremden Moduln gebildet:

A=3\cdot4\cdot5=60

Somit lauten die A_i=\frac{A}{a_i}

A_1=\frac{60}{3}=20
A_2=\frac{60}{4}=15
A_3=\frac{60}{5}=12

Mit dem erweiterten euklidischen Algorithmus lassen sich ganze Zahlen r_i und s_i mit r_i\cdot a_i+s_i \cdot A_i=1 finden:

7\cdot3+\left(-1\right)\cdot20=1
7\cdot4+\left(-1\right)\cdot15=1
5\cdot5+\left(-2\right)\cdot12=1

Es gilt also für e_i=s_i \cdot A_i:

e_1=\left(-1\right)\cdot20=-20
e_2=\left(-1\right)\cdot15=-15
e_3=\left(-2\right)\cdot12=-24

Weiterhin gilt:

e_1\cdot\ x_1=-20\cdot2=-40
e_2\cdot\ x_2=-15\cdot3=-45
e_3\cdot\ x_3=-24\cdot2=-48

Eine Lösung der simultanen Kongruenz lautet demnach

x=\sum_{i=1}^{n}{x_i\cdot e_i}=-40+\left(-45\right)+\left(-48\right)=-133

Aufgrund der Tatsache -133\equiv47\mathrm{\mathrm{\ (}mod\ }60) sind also alle Lösungen kongruent zu 47 modulo 60.

Beispiel: Chinesischer Restsatz nicht teilerfremde Moduln

Als Beispiel einer simultanen Kongruenz nicht teilerfremder Moduln soll folgendes System betrachtet werden:

x\equiv1\mathrm{\mathrm{\ (}mod\ }2)
x\equiv1\mathrm{\mathrm{\ (}mod\ }3)
x\equiv1\mathrm{\mathrm{\ (}mod\ }4)
x\equiv1\mathrm{\mathrm{\ (}mod\ }5)
x\equiv1\mathrm{\mathrm{\ (}mod\ }6)
x\equiv0\mathrm{\mathrm{\ (}mod\ }7)

Hier sind nun einige Kongruenzaussagen redundant. Diese lassen sich finden, indem die Moduln als Produkt von Primzahlpotenzen geschrieben werden. Es folgt:

x\equiv1\mathrm{\mathrm{\ (}mod\ }2)
x\equiv1\mathrm{\mathrm{\ (}mod\ }3)
x\equiv1\mathrm{\mathrm{\ (}mod\ }2^2)
x\equiv1\mathrm{\mathrm{\ (}mod\ }5)
x\equiv1\mathrm{\mathrm{\ (}mod\ }2\cdot3)
x\equiv0\mathrm{\mathrm{\ (}mod\ }7)

Die Kongruenzaussage x\equiv1\mathrm{\mathrm{\ (}mod\ }2\cdot3) ist äquivalent dazu, dass x\equiv1\mathrm{\mathrm{\ (}mod\ }2) und x\equiv1\mathrm{\mathrm{\ (}mod\ }3) gilt. Das System ist also äquivalent zu:

x\equiv1\mathrm{\mathrm{\ (}mod\ }2)
x\equiv1\mathrm{\mathrm{\ (}mod\ }3)
x\equiv1\mathrm{\mathrm{\ (}mod\ }2^2)
x\equiv1\mathrm{\mathrm{\ (}mod\ }5)
x\equiv1\mathrm{\mathrm{\ (}mod\ }2)
x\equiv1\mathrm{\mathrm{\ (}mod\ }3)
x\equiv0\mathrm{\mathrm{\ (}mod\ }7)

Hier sind nun einige Forderungen doppelt genannt. Außerdem ist x\equiv1\mathrm{\mathrm{\ (}mod\ }2^2) eine Forderung, welche die Forderung x\equiv1\mathrm{\mathrm{\ (}mod\ }2) bereits beinhaltet. Daher vereinfacht sich das System zu:

x\equiv1\mathrm{\mathrm{\ (}mod\ }3)
x\equiv1\mathrm{\mathrm{\ (}mod\ }2^2)
x\equiv1\mathrm{\mathrm{\ (}mod\ }5)
x\equiv0\mathrm{\mathrm{\ (}mod\ }7)

In diesem System treten nur paarweise teilerfremde Moduln auf und es lässt sich somit auf bekannte Art und Weise lösen.


Andere Nutzer halten diese Inhalte aus dem Bereich „Höhere Mathematik“ für besonders klausurrelevant

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.