Simultane Kongruenzen

14.05.2007, 20:34

Flo rian

Simultane Kongruenzen

Kann ich den chinesischen Restsatz immer anwenden oder gibt es eine Einschränkung?

Konkret soll ich diese 2 Gleichungssysteme lösen:

$\begin{eqnarray*} x\equiv 2 mod 3 \end{eqnarray*}$
$\begin{eqnarray*} x\equiv 2 mod 9 \end{eqnarray*}$
$\begin{eqnarray*} x\equiv 1 mod 10 \end{eqnarray*}$

$\begin{eqnarray*} x\equiv 1 mod 5 \end{eqnarray*}$
$\begin{eqnarray*} x\equiv 3 mod 9 \end{eqnarray*}$
$\begin{eqnarray*} x\equiv 1 mod 10 \end{eqnarray*}$

Wann gibt es keine Lösung?

Liebe Grüße
Flo

14.05.2007, 20:37

therisen

Auf diesen Beitrag antworten »

Ohne weiteres nein, da die Moduln nicht koprim sind. Wie es trotzdem geht, kannst du hier nachlesen: http://de.wikipedia.org/wiki/Chinesische...llgemeiner_Fall

14.05.2007, 20:41

Flo rian

Auf diesen Beitrag antworten »

Danke und wann weiß ich, dass es sicher keine Lösung gibt?

14.05.2007, 20:43

Flo rian

Auf diesen Beitrag antworten »

Rechnen in Z50
Wie kann ich in $\begin{eqnarray*} \mathbb Z_{50} \end{eqnarray*}$

$\begin{eqnarray*} [3]^{(2^{32})} \end{eqnarray*}$

berechnen?

Liebe Grüße
Flo

14.05.2007, 20:54

Auf diesen Beitrag antworten »

Hübscher Gedankensprung - bleiben wir erstmal hier:

Zitat:

Original von Flo rian
Danke und wann weiß ich, dass es sicher keine Lösung gibt?

Das ergibt sich im Laufe des Verfahrens, welches therisen verlinkt hat.

In deinen Beispielen oben ist mit geübten Auge allerdings auch so sofort zu sehen, dass beide Systeme eine Lösung haben: Da aus $\begin{eqnarray*} x\equiv a\mod mn \end{eqnarray*}$ sofort auch $\begin{eqnarray*} x\equiv a\mod n \end{eqnarray*}$ folgt, ist im ersten System die Kongruenz $\begin{eqnarray*} x\equiv 2\mod 3 \end{eqnarray*}$ bereits in $\begin{eqnarray*} x\equiv 2\mod 9 \end{eqnarray*}$ enthalten, kann also weggelassen werden. Das Restsystem genügt den Bedingungen des "normalen" Chinesischen Restsatzes mit teilerfremden Modulen.

Analog ist im zweiten System die Kongruenz $\begin{eqnarray*} x\equiv 1\mod 5 \end{eqnarray*}$ bereits in $\begin{eqnarray*} x\equiv 1\mod 10 \end{eqnarray*}$ enthalten; erstere kann also wiederum weggelassen werden.

EDIT: Die Z50-Aufgabe hast du inzwischen in einem eigenen Thread wiederholt, gut so:

Rechen in Z50

Neue Frage »

Antworten »

Simultane Kongruenzen

Verwandte Themen