Wie findet man teilerfremde Zahlen?

Teilerfremde Zahlen findet man, indem man für ein Zahlenpaar den berechnet und nur Paare mit auswählt. Den bestimmt man zum Beispiel mit dem euklidischen Algorithmus. Konkret: , also sind 8 und 15 teilerfremd, nicht.

Was besagt der Restsatz von Sun Tzu?

Der Restsatz von Sun Tzu besagt, dass ein System simultaner Kongruenzen eine Lösung besitzt, wenn die Moduln paarweise teilerfremd sind. Außerdem ist jede Lösung eindeutig bestimmt modulo .

Was sind Ideale in Ringen?

Ein Ideal in einem Ring ist eine Teilmenge, die unter Addition abgeschlossen ist und mit jedem Ringelement kompatibel bleibt, also bei Multiplikation mit beliebigen Ringelementen wieder im Ideal liegt. In sind Ideale genau die Mengen aller Vielfachen einer Zahl .

Was ist ein Faktorring?

Einen Faktorring erhält man, indem man Elemente von als gleich betrachtet, sobald sie sich um ein Element aus dem Ideal unterscheiden. Die Elemente von sind dann Restklassen und man rechnet mit ihnen wie mit Resten modulo .

Video

Hier geht's zum Video „Injektiv Surjektiv Bijektiv“

Chinesischer Restsatz

Wichtige Inhalte in diesem Video

Chinesischer Restsatz für ganze Zahlen

(00:12)

Simultane Kongruenzen ganzer Zahlen

(01:02)

Beispiel: Chinesischer Restsatz teilerfremde Moduln

(03:19)

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!

Inhaltsübersicht

Chinesischer Restsatz für allgemeine Ringe

Der chinesische Restsatz trifft eine Aussage über die Isomorphie zwischen einem Faktorring modulo des Schnittes koprimer Ideale a_i und dem Produkt der Faktorringe 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 ein Ring und seien $a_1, \dots ,a_n$ Ideale von 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 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 .

Studyflix vernetzt: Hier ein Video aus einem anderen Bereich

Chinesischer Restsatz für ganze Zahlen

im Videozur Stelle im Video springen

(00:12)

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

im Videozur Stelle im Video springen

(01:02)

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 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 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 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 kongruent zu 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 und 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 und :

A|(y-x)

Das heißt die weitere Lösung der simultanen Kongruenz ist kongruent zur Lösung 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

im Videozur Stelle im Video springen

(03:19)

Gesucht sei eine ganze Zahl 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$
$4\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:

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.

Chinesischer Restsatz — häufigste Fragen

(ausklappen)

Wie findet man teilerfremde Zahlen?

Teilerfremde Zahlen findet man, indem man für ein Zahlenpaar den $\operatorname{ggT}$ berechnet und nur Paare mit $\operatorname{ggT} = 1$ auswählt. Den $\operatorname{ggT}$ bestimmt man zum Beispiel mit dem euklidischen Algorithmus. Konkret: $\operatorname{ggT}(8,15)=1$ , also sind 8 und 15 teilerfremd, $\operatorname{ggT}(6,15)=3$ nicht.
Was besagt der Restsatz von Sun Tzu?

Der Restsatz von Sun Tzu besagt, dass ein System simultaner Kongruenzen $x \equiv x_i \pmod{a_i}$ eine Lösung besitzt, wenn die Moduln $a_1, \dots, a_n$ paarweise teilerfremd sind. Außerdem ist jede Lösung eindeutig bestimmt modulo $a_1 \cdots a_n$ .
Was sind Ideale in Ringen?

Ein Ideal in einem Ring ist eine Teilmenge, die unter Addition abgeschlossen ist und mit jedem Ringelement kompatibel bleibt, also bei Multiplikation mit beliebigen Ringelementen wieder im Ideal liegt. In $\mathbb{Z}$ sind Ideale genau die Mengen $n\mathbb{Z}$ aller Vielfachen einer Zahl .
Was ist ein Faktorring?

Einen Faktorring erhält man, indem man Elemente von als gleich betrachtet, sobald sie sich um ein Element aus dem Ideal unterscheiden. Die Elemente von sind dann Restklassen und man rechnet mit ihnen wie mit Resten modulo .

Zahlentheorie verstehen

Der chinesische Restsatz gehört zur Zahlentheorie und ist ein wichtiges Thema in der Mathematik und Informatik. Wer sich mit Zahlentheorie beschäftigt, arbeitet mit Teilbarkeit, Kongruenzen und ganzen Zahlen. So wird klar, wie sich Rechenregeln für Modulo-Aufgaben aufbauen und wie verschiedene Aussagen über Zahlen zusammenhängen. Im Informatikbereich findest du passende Videos zu diesem und verwandten Themen.

zur Videoseite: Chinesischer Restsatz