Umformung Simultaner Kongruenzen für Anwendung des chinesischen Restsatzes

14.08.2017, 12:21

goldenDiMa

Umformung Simultaner Kongruenzen für Anwendung des chinesischen Restsatzes

Meine Frage:
Hallo,

Ich habe eine Frage zum Lösen simultaner Kongruenzen. Bisher habe ich mehrere Aufgaben der Form:

x = a1 mod m1
x = a2 mod m2
...
x = an mod mn

mit Hilfe des Chinesischen Restsatz lösen können. Nun habe ich eine Aufgabe, in der das x mit unterschiedlichen Konstanten multipliziert wird, z.B.:

73x = 365 mod 10001
30x = 99 mod 243

Meine Ideen:
Ich möchte gerne wieder ein System haben, indem auf der linken Seite nur "x" steht. Kann mir jemand sagen, wie man die Kongruenzen am geschicktesten umformt, um den Chinesischen Restsatz nach Schema F anwenden zu können.

14.08.2017, 12:57

Elvis

Auf diesen Beitrag antworten »

Zum Teil hilft hier $\begin{eqnarray*} ab\equiv ac\mod m\Leftrightarrow m|a(b-c) \end{eqnarray*}$ , zum anderen kannst du $\begin{eqnarray*} 10y=x \end{eqnarray*}$ setzen.

14.08.2017, 13:05

HAL 9000

Auf diesen Beitrag antworten »

Ja, die Primfaktorzerlegung von 10001 ist gerade bei dieser Kongruenz sehr aufschlussreich. Augenzwinkern

Generell ist es m.E. hilfreich, lösbare Kongruenzen $\begin{align*} ax\equiv b\bmod m \end{align*}$ (d.h. solche mit $\begin{align*} \operatorname{ggT}(a,m) \mid b \end{align*}$ ) durch $\begin{align*} g:=\operatorname{ggT}(a,m) \end{align*}$ zu teilen, d.h., man betrachtet statt der Originalkongruenz die Kongruenz $\begin{align*} a'x\equiv b'\bmod m' \end{align*}$ mit $\begin{align*} a'=\frac{a}{g},b'=\frac{b}{g} \end{align*}$ und $\begin{align*} m'=\frac{m}{g} \end{align*}$ . Das vereinfacht dann einige Betrachtungen.

14.08.2017, 15:17

goldenDiMa

Auf diesen Beitrag antworten »

Ich sehe es noch nicht.

Mit der Primfaktorzerlegung erhalte ich für die erste Kongruenz

$\begin{eqnarray*} 73 x \equiv 365 mod 10001 \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow 73x \equiv 5 * 73 mod 137 * 73 \end{eqnarray*}$

Im ersten Moment dachte ich, dass ich die 73 als Faktor überall wegfallen lassen kann, aber das ist ja falsch, da

$\begin{eqnarray*} a*m mod m = 0 \end{eqnarray*}$

Die Anmerkung, dass ich $\begin{eqnarray*} x = 10y \end{eqnarray*}$ setzten kann habe ich nicht verstanden. Was ist das für ein y und wo kommt das her?

14.08.2017, 15:25

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von goldenDiMa
$\begin{eqnarray*} \Rightarrow 73x \equiv 5 * 73 mod 137 * 73 \end{eqnarray*}$

Im ersten Moment dachte ich, dass ich die 73 als Faktor überall wegfallen lassen kann

Wenn du mit "wegfallen" es so meinst, wie ich es geschrieben habe, dann ist das durchaus richtig, mit anderen Worten:

Die Menge der ganzen Zahlen $\begin{align*} x \end{align*}$ , die die Kongruenz $\begin{align*} 73x\equiv 5\cdot 73\bmod (137\cdot 73) \end{align*}$ lösen ist gleich der Menge derjenigen ganzen Zahlen $\begin{align*} x \end{align*}$ , die die Kongruenz $\begin{align*} x\equiv 5\bmod 137 \end{align*}$ lösen.

Das ist eine Konsequenz aus dem von Elvis erwähnten

Zitat:

Original von Elvis
$\begin{eqnarray*} ab\equiv ac\bmod m\Leftrightarrow m|a(b-c) \end{eqnarray*}$

Zitat:

Original von goldenDiMa
Die Anmerkung, dass ich $\begin{eqnarray*} x = 10y \end{eqnarray*}$ setzten kann habe ich nicht verstanden.

Habe ich auch nicht verstanden. Vielleicht ist es so gemeint: Statt $\begin{align*} x \end{align*}$ betrachten wir $\begin{align*} y=10x \end{align*}$ , dann kann man die zweite Kongruenz direkt als $\begin{align*} y\equiv 33\bmod 81 \end{align*}$ lesen. Und die erste verwandelt sich durch Multiplikation mit 10 in $\begin{align*} y\equiv 50\bmod 137 \end{align*}$ . smile

Die so gefundene Lösung $\begin{align*} y\bmod (137\cdot 81) \end{align*}$ kann dann auf $\begin{align*} x \end{align*}$ zurückgerechnet werden.

Oder aber man geht so vor: Man löst zuerst die zweite Kongruenz $\begin{align*} 10x\equiv 33\bmod 81 \end{align*}$ . Das kann auf verschiedenen Wegen geschehen, z.B. indem man zuerst $\begin{align*} 10^{-1}\equiv -8\bmod 81 \end{align*}$ ermittelt (mit EEA oder aber durch Probieren) und dann $\begin{align*} x\equiv 10^{-1}\cdot 33\equiv (-8)\cdot 33\equiv 60\bmod 81 \end{align*}$ rechnet. Damit kannst du dann den Chinesischen Restsatz auf das verbleibende

$\begin{align*} x&\equiv 5\bmod 137<br /> x&\equiv 60\bmod 81 \end{align*}$

loslassen, das war ja deine ursprüngliche Intention - oder?

15.08.2017, 22:28

goldenDiMa

Auf diesen Beitrag antworten »

Ja, mit dem Ergebnis komme ich mit dem Restsatz weiter.

Der Tipp

Zitat:

Generell ist es m.E. hilfreich, lösbare Kongruenzen ax≡bmodm (d.h. solche mit ggT(a,m)∣b) durch g:=ggT(a,m) zu teilen, d.h., man betrachtet statt der Originalkongruenz die Kongruenz a′x≡b′modm′ mit a′=ag,b′=bg und m′=mg.

ist glaube ich sehr gut und bietet scheinbar oft einen brauchbaren Ansatz.

Vielen Dank!

16.08.2017, 09:37

HAL 9000

Auf diesen Beitrag antworten »

Nicht nur oft, sondern immer! Bei einem solchen System linearer Kongruenzen kann man sich zunächst mal jede einzelne Kongruenz $\begin{align*} ax\equiv b\bmod m \end{align*}$ vorknöpfen und lösen, und das geht ja üblicherweise so:

- Bestimme $\begin{align*} g:=\operatorname{ggT}(a,m) \end{align*}$ .
- Ist $\begin{align*} g \not\mid b \end{align*}$ , dann hat diese Kongruenz und damit dann aber auch das ganze System keine Lösung!
- Ist $\begin{align*} g \mid b \end{align*}$ , so ersetzt man die Kongruenz durch $\begin{align*} a'x\equiv b'\bmod m' \end{align*}$ , mit $\begin{align*} a'=\frac{a}{g},b'=\frac{b}{g},m'=\frac{m}{g} \end{align*}$ . (Im Fall g=1 ist da natürlich überhaupt nichts zu tun.)
- Nunmehr ist $\begin{align*} \operatorname{ggT}(a',m')=1 \end{align*}$ gesichert, und diese Kongruenz $\begin{align*} a'x\equiv b'\bmod m' \end{align*}$ hat die eindeutige Lösung $\begin{align*} x \equiv (a')^{-1}b'\bmod m' \end{align*}$ , wobei die Inverse natürlich modulo m' zu verstehen ist.

Neue Frage »

Antworten »

Umformung Simultaner Kongruenzen für Anwendung des chinesischen Restsatzes

Verwandte Themen