Modulo berechnen

22.07.2014, 08:42

Rolf2014

Modulo berechnen

Meine Frage:
Hallo,

ich versuche als mehr oder weniger Laie folgendes Gleichungssystem zu lösen:

1 = x mod 5
2 = x mod 6

Mir ist klar, dass eine mögliche Lösung zum Beispiel 26 wäre, aber wie berechne ich hierzu eine Formel?

Meine Ideen:
Aus der o.g. Formel lässt sich für ganze Zahlen dieses hier ableiten:
x = 5k + 1
x = 6m + 2

Mir fehlt jetzt so Recht der Ansatz. Wie gesagt, ich bin Leihe aber ich mich interessiert hier die Herangehensweise.

22.07.2014, 09:01

HAL 9000

Auf diesen Beitrag antworten »

Es gibt natürlich eine ausführliche Theorie inklusive genau beschriebenen Lösungsverfahren für solche simultanen linearen Kongruenzen:

http://de.wikipedia.org/wiki/Chinesischer_Restsatz

Für einfache Fälle wie hier kann man auch "pragmatisch" kürzer rangehen, wenn man nicht den ganzen Apparat auffahren will: Nehmen wir zum Start deine Lösung $\begin{align*} x=6m+2 \end{align*}$ der zweiten Kongruenz, und die setzen wir in die erste Kongruenz ein, das ergibt

$\begin{align*} 1 \equiv 6m+2 \equiv m+2 \bmod 5 \end{align*}$ ,

das ist umgestellt $\begin{align*} m\equiv -1 \equiv 4\bmod 5 \end{align*}$ , was man als $\begin{align*} m=5n+4 \end{align*}$ schreiben kann. Und das führt zur Lösung $\begin{align*} x= 6m+2 = 6(5n+4)+2 = 30n+26 \end{align*}$ .

22.07.2014, 09:33

Rolf2014

Auf diesen Beitrag antworten »

Vielen Dank, ich habe es halbwegs verstanden. Jedoch ist mir nicht klar, wie aus

$\begin{align*} 1 \equiv 6m+2 \equiv m+2 \bmod 5 \end{align*}$ ,

das hier wird:

$\begin{align*} m\equiv -1 \equiv 4\bmod 5 \end{align*}$

Edit: bzw. der Schritt ist mir schon klar, aber müsste es nicht m mod 5 lauten?

22.07.2014, 10:05

HAL 9000

Auf diesen Beitrag antworten »

Also $\begin{align*} 1\equiv m+2\bmod 5 \end{align*}$ ist noch klar? Dann einfach 2 subtrahieren...

22.07.2014, 10:20

Rolf2014

Auf diesen Beitrag antworten »

Wahrscheinlich mangelt's mir da an dem Background smile

Aber müsste es nicht so lauten:

$\begin{align*} 1 \equiv 6m+2 \equiv m+2 \bmod 5 \equiv 2 + m \bmod 5 \end{align*}$

daraus folgend:

$\begin{align*} m \bmod 5 \equiv -1 \end{align*}$

Oder wieso ist m auf einmal freigestellt?

Danke für die Geduld!

22.07.2014, 11:08

HAL 9000

Auf diesen Beitrag antworten »

Ich rede nicht von dem zweistelligen Modulo-Operator $\begin{align*} a\bmod b \end{align*}$ (d.h. Rest bei der Division von a durch b), sondern von der Restklassenkongruenz $\begin{align*} a\equiv b\bmod m \end{align*}$ . unglücklich

Siehe http://de.wikipedia.org/wiki/Kongruenz_%28Zahlentheorie%29

22.07.2014, 11:24

Rolf2014

Auf diesen Beitrag antworten »

Alles klar, hab's jetzt komplett verstanden! Für mich geriet das etwas durcheinander, da mir der Bezug dazu fehlte.

Jetzt ist es klar, danke!

22.07.2014, 13:31

Rolf2014

Auf diesen Beitrag antworten »

Jetzt habe ich doch noch eine Frage, warum komme ich nicht zu dem Ergebnis wenn ich das umgekehrt angehe? Also:

$\begin{eqnarray*} 2 \equiv 5k + 1 \equiv k + 1 mod 6 \end{eqnarray*}$

$\begin{eqnarray*} k \equiv 1 mod 6 \end{eqnarray*}$

$\begin{eqnarray*} k = 6p + 1 \end{eqnarray*}$

$\begin{eqnarray*} x = 5k + 1 = 5 (6p + 1) + 1 = 30p + 6 \end{eqnarray*}$

Habe ich irgendwo einen Denk- bzw. Rechenfehler? Statt +6 sollte dort ja eigentlich +26 richtig sein.

22.07.2014, 17:14

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Rolf2014
Jetzt habe ich doch noch eine Frage, warum komme ich nicht zu dem Ergebnis wenn ich das umgekehrt angehe? Also:

$\begin{eqnarray*} 2 \equiv 5k + 1 \equiv k + 1 mod 6 \end{eqnarray*}$

Anscheinend hast du nicht so richtig erfasst, was da oben passiert ist: Das oben von mir vereinfachte $\begin{align*} 6m\equiv m\bmod 5 \end{align*}$ geschah auf der Grundlage von $\begin{align*} 6\equiv 1\bmod 5 \end{align*}$ .

Deine Überlegung hier $\begin{align*} 5k\equiv k\bmod 6 \end{align*}$ ist aber falsch, denn es ist ja nicht $\begin{align*} 5\equiv 1\bmod 6 \end{align*}$ , sondern $\begin{align*} 5\equiv -1\bmod 6 \end{align*}$ . Wenn du hier also so ähnlich rechnen willst, dann doch bitte mit

$\begin{align*} 5k+1 \equiv -k+1 \bmod 6 \end{align*}$ .

23.07.2014, 05:52

Rolf2014

Auf diesen Beitrag antworten »

Okay, auch das habe ich jetzt begriffen.

Danke, hab ne Menge an der Aufgabe gelernt.

Neue Frage »

Antworten »

Modulo berechnen

Verwandte Themen