Chinesischer Restsatz Beweis

20.02.2012, 14:33

kretek

Chinesischer Restsatz Beweis

Meine Frage:
Hallo,
ich versuche den Beweis des Chinesischen Restsatzes in meinem Skript zu verstehen, allerdings kann ich einige Schritte nicht nachvollziehen.

Der Satz ist folgendermaßen definiert:

Sei R ein HIB und ein system simultaner Kongruenzen
$\begin{eqnarray*} x \equiv c_{1}(modb_{1}) \end{eqnarray*}$
usw
$\begin{eqnarray*} x \equiv c_{n}(mod b_{n}) \end{eqnarray*}$
wobei $\begin{eqnarray*} ggT(b_{i}, b_{j})= 1 \end{eqnarray*}$ für i ungleich j
Sei $\begin{eqnarray*} B_{i}= b_{1}...b_{i-1} b_{i+1}...b_{n} \end{eqnarray*}$
Dann gilt $\begin{eqnarray*} ggT(b_{i}, B_{i})= 1 \end{eqnarray*}$
Also gibt es ri, si: $\begin{eqnarray*} r_{i}b_{i}+s_{i}B_{i}= 1 \end{eqnarray*}$
Setze $\begin{eqnarray*} d_{i}= s_{i} B_{i} \end{eqnarray*}$
Dann ist das System von Kongruenzen äquivalent zu
$\begin{eqnarray*} x\equiv \sum\limits_{i=1}^n c_{i}d_{i} (mod b_{1}...b_{n}) \end{eqnarray*}$

Meine Ideen:
Rückrichtung

Sei also $\begin{eqnarray*} x\equiv \sum\limits_{i=1}^n c_{i}d_{i} (mod b_{1}...b_{n}) \end{eqnarray*}$
Dann kann ich das ganze für ein q aus R doch auch folgendermaßen schreiben: $\begin{eqnarray*} x= qb_{1}...b_{n} +\sum\limits_{i=1}^n c_{i}d_{i} \end{eqnarray*}$
Im dem Skript steht aber $\begin{eqnarray*} x= qb_{1}...b_{n} +\sum\limits_{j=1}^n c_{j}d_{j} \end{eqnarray*}$
Warum mit j ?

Dann ist $\begin{eqnarray*} x \equiv\sum\limits_{i=1}^n c_{j}d_{j}(mod b_{i}) \end{eqnarray*}$
Hier steht schon wieder ein j. Muss da nicht ein i hin?
Vielleicht verstehe ich den Rest des Beweises alleine, wenn dieses Problem geklärt ist Augenzwinkern

Liebe Grüße

21.02.2012, 10:10

Reksilat

Auf diesen Beitrag antworten »

RE: Chinesischer Restsatz Beweis
Hi kretek,

Es ist völlig egal, ob Du über $\begin{eqnarray*} i \end{eqnarray*}$ oder über $\begin{eqnarray*} j \end{eqnarray*}$ summierst. Die Ausdrücke $\begin{eqnarray*} \sum_{i=1}^nc_id_i \end{eqnarray*}$ und $\begin{eqnarray*} \sum_{j=1}^nc_jd_j \end{eqnarray*}$ sind identisch. Beides ist $\begin{eqnarray*} c_1d_1+c_2d_2+...+c_nd_n \end{eqnarray*}$

Zitat:

$\begin{eqnarray*} x \equiv\sum\limits_{i=1}^n c_{j}d_{j}(mod b_{i}) \end{eqnarray*}$
Hier steht schon wieder ein j. Muss da nicht ein i hin?

Hier ergibt das $\begin{eqnarray*} j \end{eqnarray*}$ keinen Sinn, denn $\begin{eqnarray*} j \end{eqnarray*}$ ist nur innerhalb der Summe $\begin{eqnarray*} \sum_{j=1}^n... \end{eqnarray*}$ definiert, wenn man es nicht anderweitig festgelegt hat.

Ich würde eher schreiben:
Für jedes $\begin{eqnarray*} i\in\{1,...,n\} \end{eqnarray*}$ gilt:
$\begin{eqnarray*} x \equiv\sum\limits_{j=1}^n c_{j}d_{j}\pmod{b_{i}} \end{eqnarray*}$

Gruß,
Rubiksilat.

23.02.2012, 18:42

kretek

Auf diesen Beitrag antworten »

RE: Chinesischer Restsatz Beweis
Ich habe noch eine Frage zur Hinrichtung.

Wir haben jetzt ja die beiden Darstellungen

$\begin{eqnarray*} x\equiv \sum\limits_{i=1}^n c_{i}d_{i} (mod b_{1}...b_{n}) \end{eqnarray*}$
und
$\begin{eqnarray*} x\equiv \sum\limits_{j=1}^n c_{j}d_{j} (mod b_{i}) \end{eqnarray*}$

Jetzt kann ich $\begin{eqnarray*} d_{i} \end{eqnarray*}$ und $\begin{eqnarray*} d_{j} \end{eqnarray*}$ "umschreiben"

Es gilt ja nach Voraussetzung:
$\begin{eqnarray*} r_{i}b_{i}+s_{i}B_{i} = 1 \end{eqnarray*}$ und $\begin{eqnarray*} s_{i}B_{i}= d{i} \end{eqnarray*}$

Also $\begin{eqnarray*} d_{i}= 1-r_{i}b_{i} \end{eqnarray*}$
und es folgt $\begin{eqnarray*} d_{i}= 1 (modb_{i}) \end{eqnarray*}$

Weiter gilt nach Voraussetzung

$\begin{eqnarray*} d_{j}= s_{1}b_{1}...b_{j-1}b_{j+1}...b_{n} \end{eqnarray*}$
Dann kann ich z.B. die Stelle $\begin{eqnarray*} b_{j-1} \end{eqnarray*}$ als $\begin{eqnarray*} b_{i} \end{eqnarray*}$ betrachten und es gilt $\begin{eqnarray*} d_{j}= 0(mod b_{i}) \end{eqnarray*}$

Ich verstehe nicht ganz, warum daraus jetzt folgt:
$\begin{eqnarray*} x\equiv c_{i}(mod b_{i}) \end{eqnarray*}$

Liebe Grüße

23.02.2012, 19:04

Reksilat

Auf diesen Beitrag antworten »

RE: Chinesischer Restsatz Beweis
Na Du hast doch:
$\begin{eqnarray*} x\equiv \sum\limits_{j=1}^n c_{j}d_{j} \pmod{b_{i}} \end{eqnarray*}$

Und für $\begin{eqnarray*} j\neq i \end{eqnarray*}$ ist $\begin{eqnarray*} d_j\equiv 0\pmod{b_i} \end{eqnarray*}$

Damit bleibt von der Summe nur noch der Summand an der Stelle $\begin{eqnarray*} i \end{eqnarray*}$ übrig:
$\begin{eqnarray*} x\equiv c_{i}d_{i} \pmod {b_{i}} \end{eqnarray*}$

Aber $\begin{eqnarray*} d_i\equiv 1\pmod{b_i} \end{eqnarray*}$

24.02.2012, 13:32

kretek

Auf diesen Beitrag antworten »

RE: Chinesischer Restsatz Beweis
oh ja, stimmt Hammer

danke

Neue Frage »

Antworten »

Chinesischer Restsatz Beweis

Verwandte Themen