Lösen einer Gleichung aus der Kongruenzrechnung (Zahlentheorie)

30.05.2009, 20:08

Pejosh

Lösen einer Gleichung aus der Kongruenzrechnung (Zahlentheorie)

Hallo,

ich soll eine Aufgabe lösen, von der ich gar nicht weiß, wie ich sie angehen soll.

Sie lautet:

Geben Sie alle Lösungen der folgenden Gleichung an: $\begin{eqnarray*} (x-5)(x-3)\equiv 0 mod77 \end{eqnarray*}$ .

Kann ich die Gleichung in die folgenden zwei Gleichungen unterteilen?

$\begin{eqnarray*} (x-5)\equiv 0 mod77 \end{eqnarray*}$
$\begin{eqnarray*} (x-3)\equiv 0 mod77 \end{eqnarray*}$

Da ich den Chinesischen Restsatz nicht wirklich verstanden habe, und mir alle immer sagen, dass ich das damit lösen muss, stehe ich total auf dem Schlauch. Bin für jede Anregung sehr dankbar!

LG, Pejosh

31.05.2009, 10:01

Huggy

Auf diesen Beitrag antworten »

RE: Lösen einer Gleichung aus der Kongruenzrechnung (Zahlentheorie)

Zitat:

Original von Pejosh

Kann ich die Gleichung in die folgenden zwei Gleichungen unterteilen?

$\begin{eqnarray*} (x-5)\equiv 0 mod77 \end{eqnarray*}$
$\begin{eqnarray*} (x-3)\equiv 0 mod77 \end{eqnarray*}$

Das ist nicht ausreichend. Wenn eine dieser beiden Kongruenzen erfüllt ist, ist natürlich die zu lösende Kongruenz erfüllt. Wegen 77 = 7*11 musst du aber zusätzlich folgende Fälle betrachten:

$\begin{eqnarray*} x-5\equiv 0\quad mod \quad 7 \end{eqnarray*}$ und $\begin{eqnarray*} x-3\equiv 0 \quad mod \quad 11 \end{eqnarray*}$
bzw.
$\begin{eqnarray*} x-5\equiv 0\quad mod \quad 11 \end{eqnarray*}$ und $\begin{eqnarray*} x-3\equiv 0 \quad mod \quad 7 \end{eqnarray*}$

Auf diese simultanen Kongruenzen kannst du den chinesischen Restesatz anwenden. Gesunder Menschenverstand reicht aber auch.

31.05.2009, 12:21

Pejosh

Auf diesen Beitrag antworten »

Erstmal vielen Dank für deine Hilfe. So etwas hatte ich mir gedacht, aber nicht so ganz verstanden wieso. Wenn ich das aber erstmal so mache, dann nehme ich mir mal deine ersten 2 Gleichungen vor.

$\begin{eqnarray*} x-5\equiv 0 mod 7 \end{eqnarray*}$ und $\begin{eqnarray*} x-3\equiv 0 mod11 \end{eqnarray*}$ ist ja gleichbedeutend mit

$\begin{eqnarray*} x\equiv 5 mod 7 \end{eqnarray*}$ und $\begin{eqnarray*} x\equiv 3 mod11 \end{eqnarray*}$

Mit dem chinesischen Restsatz folgt dann doch:

$\begin{eqnarray*} e_1=0 mod 7 \end{eqnarray*}$ und $\begin{eqnarray*} e_1=1 mod 11 \end{eqnarray*}$

$\begin{eqnarray*} e_2=0 mod 11 \end{eqnarray*}$ und $\begin{eqnarray*} e_2=1 mod 7 \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow e_1=56 \end{eqnarray*}$ wählbar und $\begin{eqnarray*} e_2=22 \end{eqnarray*}$ wählbar

Dann folgt nach dem Satz:

$\begin{eqnarray*} x=5\cdot 56+3\cdot 22=346 \end{eqnarray*}$

Aber jetzt weiß ich nicht, wie daraus die Lösung folgt. Schließlich soll ich ja alle x angeben. verwirrt

31.05.2009, 14:04

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von Pejosh
So etwas hatte ich mir gedacht, aber nicht so ganz verstanden wieso.

Die Kongruenz

$\begin{eqnarray*} (x-5)(x-3)\equiv \quad 0 \quad mod 77 \end{eqnarray*}$

bedeutet doch, 77 teilt $\begin{eqnarray*} (x-5)(x-3) \end{eqnarray*}$ . Dafür gibt es 4 Möglichkeiten:

(1) 77 teilt x -5
(2) 77 teilt x - 3
(3) 7 teilt x -5 und 11 teilt x -3
(4) 11 teilt x -5 und 7 teilt x -3

Jeder Fall trägt zur gesamten Lösungsmenge bei. Fall (1) hat z. B. die Lösungen

$\begin{eqnarray*} x=77n+5 \end{eqnarray*}$ mit n ganzzahlig.

Zitat:

$\begin{eqnarray*} x=5\cdot 56+3\cdot 22=346 \end{eqnarray*}$

Aber jetzt weiß ich nicht, wie daraus die Lösung folgt. Schließlich soll ich ja alle x angeben. verwirrt

Bei der Anwendung des chinesischen Restesatzes hast du $\begin{eqnarray*} e_1 \end{eqnarray*}$ und $\begin{eqnarray*} e_2 \end{eqnarray*}$ vertauscht. Das schadet ausnahmsweise nicht, weil es der Vertauschung von (3) und (4) entspricht.
Die Lösungen von (3) und (4) haben auch die Form:

$\begin{eqnarray*} x=77n+r \end{eqnarray*}$

Wegen $\begin{eqnarray*} 346 =4\cdot77+38 \end{eqnarray*}$ ergibt das folgende Lösungen für (4):

$\begin{eqnarray*} x=77n+38 \end{eqnarray*}$

Bleibt nur noch, (2) und (3) zu ergänzen.

31.05.2009, 16:31

Pejosh

Auf diesen Beitrag antworten »

Jetzt hab ich verstanden, warum es diese Möglichkeiten gibt! Mit Zunge

Wenn ich jetzt mal deine Bezeichnung übernehme, folgt jeweils:

(1) $\begin{eqnarray*} \Rightarrow x=77n+5 \end{eqnarray*}$
(2) $\begin{eqnarray*} \Rightarrow x=77k+3 \end{eqnarray*}$
(3) $\begin{eqnarray*} \Rightarrow x=77l+38 \end{eqnarray*}$
(4) $\begin{eqnarray*} \Rightarrow x=77m+47 \end{eqnarray*}$

mit $\begin{eqnarray*} k,l,m,n\in \mathbb{Z} \end{eqnarray*}$ .

Ich muss diese 4 Gleichungen doch sicherlich noch in eine basteln, oder? Bleibt nur die Frage wie. Einfach addieren ist wohl nicht erlaubt. verwirrt

31.05.2009, 16:34

Pejosh

Auf diesen Beitrag antworten »

Zitat:

Original von Pejosh
(4) $\begin{eqnarray*} \Rightarrow x=77m+47 \end{eqnarray*}$

Da ich bei Vertauschen von $\begin{eqnarray*} e_1 \end{eqnarray*}$ und $\begin{eqnarray*} e_2 \end{eqnarray*}$ $\begin{eqnarray*} x=278 \end{eqnarray*}$ erhalte und dies dann ja auch so umformen kann, wie du es gemacht hattest.

31.05.2009, 17:16

Huggy

Auf diesen Beitrag antworten »

Das ist jetzt korrekt. Die vier Gleichungen kann man nicht zusammenfassen. Man kann sie höchstens knapper schreiben:

$\begin{eqnarray*} x=77n+r \end{eqnarray*}$ mit $\begin{eqnarray*} n\in \mathbb{Z} \end{eqnarray*}$ und $\begin{eqnarray*} r \in \left\{3, 5, 38, 47 \right\} \end{eqnarray*}$

31.05.2009, 21:38

Pejosh

Auf diesen Beitrag antworten »

Achso, dann lass ich das einfach so stehen. Ich kann es aber auch noch so umformen, oder?

$\begin{eqnarray*} x\equiv rmod77 \end{eqnarray*}$ mit $\begin{eqnarray*} r\in \left\{ 3,5,38,47\right\} \end{eqnarray*}$

01.06.2009, 09:07

Huggy

Auf diesen Beitrag antworten »

So kann man es auch schreiben.

Neue Frage »

Antworten »

Lösen einer Gleichung aus der Kongruenzrechnung (Zahlentheorie)

Verwandte Themen