Kongruenzsystem

10.09.2005, 19:35

irre.flexiv

Kongruenzsystem

Hallo ich habe gerade arge Probleme das hier zu lösen. Klar, die Lösung sieht man sofort,
aber warum funktioniert der Lösungsalgorithmus hier nicht? verwirrt

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

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

Der Chinesische Restsatz sagt aus : wegen $\begin{eqnarray*} ggT(2,3) = 1 \end{eqnarray*}$ ist das System lösbar.
Jetzt kann man daraus das hier basteln :

$\begin{eqnarray*} u = 1 + 2t = 2 + 3s \quad s,t \in \mathbb Z \end{eqnarray*}$

$\begin{eqnarray*} 2t - 3s = 2 - 1 = 1 \end{eqnarray*}$

(Lösungsmenge ist $\begin{eqnarray*} x \equiv u \mod kgV(2,3) =6 \end{eqnarray*}$ )

Es ist klar das dann auch $\begin{eqnarray*} 2t+3s = 1 \end{eqnarray*}$ lösbar ist.
Darauf wendet man jetzt den euklidischen Algorithmus an und erhält:

$\begin{eqnarray*} 1*3+(-1)*2 = 1 \end{eqnarray*}$

nun die Umformung rückgängig machen:

$\begin{eqnarray*} 1*3 - 1*2 = 1 = 2 - 1 \end{eqnarray*}$

$\begin{eqnarray*} 1*3 +1 = 1*2 + 2 = 4 \end{eqnarray*}$

Nach dem Algorithmus wäre jetzt $\begin{eqnarray*} x \equiv 4 \mod 6 \end{eqnarray*}$ . Das ist aber falsch. Das Problem scheint immer dann aufzutreten wenn die Kongruenz $\begin{eqnarray*} x \equiv 1 \mod 2 \end{eqnarray*}$ im System auftritt. Bitte helft mir traurig

10.09.2005, 19:45

Auf diesen Beitrag antworten »

RE: Kongruenzsystem

Zitat:

Original von irre.flexiv
Nach dem Algorithmus wäre jetzt $\begin{eqnarray*} x \equiv 4 \mod 6 \end{eqnarray*}$ .

Wieso das denn?

Wenn schon, dann

$\begin{eqnarray*} x\equiv (-1)*3 +2 = (-1)*2 + 1 = -1\mod 6 \end{eqnarray*}$

10.09.2005, 20:01

irre.flexiv

Auf diesen Beitrag antworten »

Wenn das rauskäme wäre das super aber leider tut es das nicht.

Der Algorithmus um $\begin{eqnarray*} 2t+3s = 1 \end{eqnarray*}$ zu lösen läuft ja so ab:

Man bestimmt den ggT von 2 und 3 mit Euklid, hier ist es natürlich nur ein Schritt:
$\begin{eqnarray*} 3 = 1*2 + 1 \end{eqnarray*}$

Die Gleichung stellt man nun nach eins um

$\begin{eqnarray*} 1 = 1*3 -1*2 \end{eqnarray*}$

und hat somit t und s gefunden.

12.09.2005, 09:49

Auf diesen Beitrag antworten »

Richtig, man hat sie gefunden: s=1 und t=-1, also $\begin{eqnarray*} u=2t+1=-1 \end{eqnarray*}$ , und das modulo 6.

Das Problem scheint vielmehr zu sein, dass du einmal $\begin{eqnarray*} 2t-3s=1 \end{eqnarray*}$ und dann wieder $\begin{eqnarray*} 2t+3s=1 \end{eqnarray*}$ betrachtest und das dann vorzeichenmäßig durcheinander wirbelst. Bring also mal Ordnung in dein Chaos!

12.09.2005, 10:47

irre.flexiv

Auf diesen Beitrag antworten »

Hallo Arthur, ich war gerade dabei eine komplette Abhandlung über diophantische Gleichungen zu schreiben,
als deine Antwort und der entscheidende Hinweis kam Big Laugh

$\begin{eqnarray*} 1 = 2t + 3s \end{eqnarray*}$ statt $\begin{eqnarray*} 1 = 2t -3s \end{eqnarray*}$ zu betrachten ist ja nicht das Problem,
denn die beiden Gleichungen haben die selbe Lösungsmenge in $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ .

Ich hab jetzt aber nicht erkannt das eine spezielle Lösung von $\begin{eqnarray*} 1=2t+3s \end{eqnarray*}$ nicht mehr unbedingt $\begin{eqnarray*} 1+2t = 2 +3s \end{eqnarray*}$ erfüllen mus
(eben wegen dem Vorzeichenwechsel).

Wenn man statt $\begin{eqnarray*} 1+2*2 \equiv 2 +3s \mod 6 \end{eqnarray*}$ dann mit $\begin{eqnarray*} 1+2*t = 2 +3s \end{eqnarray*}$ rechnet landet man natürlich auf dem Holzweg.

Vielen Dank für den Hinweis smile

12.09.2005, 10:52

Auf diesen Beitrag antworten »

Deckt sich völlig mit meiner Erfahrung, dass Vorzeichenfehler die häufigsten überhaupt sind. Auch bei mir. Augenzwinkern

Neue Frage »

Antworten »

Kongruenzsystem

Verwandte Themen