Lineare Kongruenz

08.05.2014, 13:36

Champ 10

Lineare Kongruenz

Meine Frage:
Hallo,

Ich hätte eine Frage zu lineare Kongruenzen,
Wie gehe bei solchen Beispielen vor ?

Beispiel:

4x ? 6 (mod14)

Meine Ideen:
Also,
ich weiß, dass man den ggT(4,14)=2 zuerst bestimmen muss, dann schauen ob der 2|6. jetzt wissen wir dass es 2 Lösungen gibt.

Wendet man dann hier den erweiterten euklischen Algorithmus an und dann kann man eigentlich die 4x0 + 14yo = 2 bestimmen, dann muss man mit 3 multipilizieren, damit man auf der rechten Siet auf 6 kommt.
also ist x0 = -9, und y0=3.

Was mache ich jetzt ?

Ich danke für jede Hilfe smile

09.05.2014, 10:47

HAL 9000

Auf diesen Beitrag antworten »

Halten wir fest:

$\begin{eqnarray*} 4x \equiv 6\bmod 14 \end{eqnarray*}$ ist lösbar, da die rechte Seite 6 durch $\begin{eqnarray*} g:=\operatorname{ggT}(4,14)=2 \end{eqnarray*}$ teilbar ist.

Per EEA hast du eine Lösung $\begin{eqnarray*} x_0=-3,y_0=1 \end{eqnarray*}$ von $\begin{eqnarray*} 4x_0+14y_0=2 \end{eqnarray*}$ ermittelt, d.h. für dieses $\begin{eqnarray*} x_0 \end{eqnarray*}$ gilt $\begin{eqnarray*} 4x_0\equiv 2\bmod 14 \end{eqnarray*}$ .

Jetzt einfach nur mit $\begin{eqnarray*} \frac{6}{g}=\frac{6}{2}=3 \end{eqnarray*}$ multiplizieren ergibt $\begin{eqnarray*} 4\cdot (3x_0)\equiv 6\bmod 14 \end{eqnarray*}$ , d.h. $\begin{eqnarray*} 3x_0\bmod 14 \end{eqnarray*}$ ist eine Lösung deiner Kongruenz. Alle $\begin{eqnarray*} g \end{eqnarray*}$ Lösungen der Kongruenz ergeben sich über

$\begin{eqnarray*} 3x_0 + k\cdot \frac{14}{g} \bmod 14 \end{eqnarray*}$ für $\begin{eqnarray*} k=0,1,\ldots,g-1 \end{eqnarray*}$ .

10.05.2014, 11:56

Champ 10

Auf diesen Beitrag antworten »

Hallo HALL 9000,

Das Ergebnis lautet aber x0=5 und 12

Also x kongruent 5 Mod 14
Und x kongruent 12 Mod 14

10.05.2014, 12:33

Champ 10

Auf diesen Beitrag antworten »

Ich kann zwar eine diophantische Gleichung lösen aber ich versteh bei dem Beispiel nicht wie x =5 und x= 12 sein kann.

Weil man müsste ja mit dieser Formel arbeiten wenn man alle x haben möchte.

X= (x0 + b/ggT(a,b)) verwirrt

10.05.2014, 17:56

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Champ 10
Das Ergebnis lautet aber x0=5 und 12

Das aber kannst du getrost streichen: Nach dem von mir beschriebenen Vorgehen und mit deinem aus dem EEA gewonnenen $\begin{eqnarray*} x_0=-3 \end{eqnarray*}$ kommen doch die beiden Lösungen

$\begin{eqnarray*} 3x_0 = -9 \equiv 5\bmod 14 \end{eqnarray*}$

sowie

$\begin{eqnarray*} 3x_0 + \frac{14}{g} = -9+7 = -2 \equiv 12\bmod 14 \end{eqnarray*}$

heraus - also wo ist das Problem? unglücklich

Ich sehe nur ein ernsthaftes Problem in deinen Ausführungen: Dass du nämlich Symbol $\begin{eqnarray*} x_0 \end{eqnarray*}$ in unterschiedlichen Bedeutungen verwendest:

Einmal als $\begin{eqnarray*} x_0=-3,y_0=1 \end{eqnarray*}$ im EEA-Ergebnis für $\begin{eqnarray*} 4x_0+14y_0 = 2 \end{eqnarray*}$ , was also $\begin{eqnarray*} 4x_0\equiv 2\bmod 14 \end{eqnarray*}$ bedeutet. Und dann redest du aber plötzlich von $\begin{eqnarray*} x_0=-9 \end{eqnarray*}$ , weil du dann an $\begin{eqnarray*} 4x_0\equiv 6\bmod 14 \end{eqnarray*}$ denkst.

So geht's nicht - wer sich das durchliest, denkt nur: Blankes Chaos in den Bezeichnungen. unglücklich

Neue Frage »

Antworten »

Lineare Kongruenz

Verwandte Themen