Lösung eines Kongruenzsystems (chinesischer Restsatz)

25.07.2021, 15:56

MMchen60

Lösung eines Kongruenzsystems (chinesischer Restsatz)

Hallo liebes Forumsgemeinde, es geht im folgende Aufgabe:
$\begin{eqnarray*} \begin{vmatrix} 26x\equiv 22\; mod \;15 \\ 16x\equiv -5\; mod \;9 \\ 80x\equiv 105\; mod \;125\\ 32x\equiv 42\; mod \;50 \end{vmatrix}<br /> \end{eqnarray*}$
Ich habe zunächst festgestellt, dass, wenn man die 3. Zeile durch 5 und die 4. Zeile durch 2 teilt, dass da dann das gleiche steht. Ich kann also die vierte Zeile weglassen und bekomme damit:
$\begin{eqnarray*} \begin{vmatrix} 26x\equiv 22\; mod \;15 \\ 16x\equiv -5\; mod \;9 \\ 16x\equiv 21\; mod \;25 \end{vmatrix}<br /> \end{eqnarray*}$
Jetzt sind die Moduli nicht teilerfremd, also schreiben wir
$\begin{eqnarray*} 26x\equiv 22\; mod \;15 = 26x\equiv 22\; mod \;3 \wedge 26x\equiv 22\; mod \;5 \end{eqnarray*}$
$\begin{eqnarray*} 16x\equiv -5\; mod \;9 = 16x\equiv -5\; mod \;3^2 = 16x\equiv -5\; mod \;3 \end{eqnarray*}$
$\begin{eqnarray*} 16x\equiv 21\; mod \;25 = 16x\equiv 21\; mod \;5^2 = 16x\equiv 21\; mod \;5 \end{eqnarray*}$
Mein endgültiges Kongruenzsystem lautet somit:
$\begin{eqnarray*} \begin{vmatrix} 26x\equiv 22\; mod \;3 \\ 26x\equiv 22\; mod \;5 \\16x\equiv -5\; mod \;3 \\ 16x\equiv 21\; mod \;5 \end{vmatrix} \end{eqnarray*}$

Ist das bis hierher richtig oder habe ich da schon einen Denkfehler?

25.07.2021, 16:19

HAL 9000

Auf diesen Beitrag antworten »

Ausschlaggebend bei den Modulen ist die höchste Primzahlpotenz, nicht die niedrigste! Richtig wäre deshalb zunächst

$\begin{eqnarray*} \begin{vmatrix} 26x\equiv 22\; mod \;3 \\ 26x\equiv 22\; mod \;5 \\16x\equiv -5\; mod \;3^2 \\ 16x\equiv 21\; mod \;5^2\end{vmatrix} \end{eqnarray*}$

Dieses System hat keine Lösung, da sich erste und dritte Kongruenz widersprechen.

D.h., ausgehend vom Originalsystem kann man die Angelegenheit in aller Kürze so abfackeln: Die ersten beiden Kongruenzen modulo 3 betrachtet bekommt man

$\begin{eqnarray*} 26x\equiv 22\bmod 3 \end{eqnarray*}$
$\begin{eqnarray*} 16x\equiv -5\bmod 3 \end{eqnarray*}$

was in der Summe $\begin{eqnarray*} 42x\equiv 17\bmod 3 \end{eqnarray*}$ , d.h., $\begin{eqnarray*} 0\equiv 2\bmod 3 \end{eqnarray*}$ bedeutet - Widerspruch.

25.07.2021, 18:27

MMchen60

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

$\begin{eqnarray*} 26x\equiv 22\bmod 3 \end{eqnarray*}$
$\begin{eqnarray*} 16x\equiv -5\bmod 3 \end{eqnarray*}$

was in der Summe $\begin{eqnarray*} 42x\equiv 17\bmod 3 \end{eqnarray*}$ , d.h., $\begin{eqnarray*} 0\equiv 2\bmod 3 \end{eqnarray*}$ bedeutet - Widerspruch.

Danke HAL9000. Das heißt aber doch, dass ich bis auf die 3^2 und 5^2 richtig lag, oder?
Noch eine Frage:
Wie kommt man von $\begin{eqnarray*} 42x\equiv 17\bmod 3 \end{eqnarray*}$ auf $\begin{eqnarray*} 0\equiv 2\bmod 3 \end{eqnarray*}$ ? Könntest du mir bitte den Rechenweg erklären? Danke.

25.07.2021, 20:33

mYthos

Auf diesen Beitrag antworten »

Da HAL nicht online ist, eine kurze Begründung:

- 17 mod 3 ist gleichbedeutend mit 2 mod 3 (17 hinterlässt bei Division durch 3 den Rest 2)
- 42 ist kongruent 0 mod 3 (42 ist restlos durch 3 teilbar), daher auch 42x

mY#

26.07.2021, 07:00

MMchen60

Auf diesen Beitrag antworten »

Zitat:

Original von mYthos
Da HAL nicht online ist, eine kurze Begründung:

- 17 mod 3 ist gleichbedeutend mit 2 mod 3 (17 hinterlässt bei Division durch 3 den Rest 2)
- 42 ist kongruent 0 mod 3 (42 ist restlos durch 3 teilbar), daher auch 42x

mY#

Danke mYthos, kapiert.
Mir kommt da aber noch eine andere Verständnisfrage. Es sollte ja heißen (nach HAL)
$\begin{eqnarray*} 16x\equiv -5\;mod\;3^2 \end{eqnarray*}$
Da $\begin{eqnarray*} 3^2 \end{eqnarray*}$ abwer gleichbedeutend ist mit $\begin{eqnarray*} 3 \cdot 3 \end{eqnarray*}$ kann ich doch schreiben
$\begin{eqnarray*} 16x\equiv -5\;mod\;3^2 =16x\equiv -5\;mod\;3 \cap 16x\equiv -5\;mod\;3 \end{eqnarray*}$
und da jetzt beide Ausrücke wieder identisch sind, darf ich doch einen weglassen, so wie es in HALs Rechnung dann ja auch eingegangen ist. Oder ?
Danke.

26.07.2021, 10:40

HAL 9000

Auf diesen Beitrag antworten »

@MMchen60

Nach deiner Ansicht sind die Kongruenzen

$\begin{eqnarray*} 16x\equiv -5\bmod 3^2 \end{eqnarray*}$ und $\begin{eqnarray*} 16x\equiv -5\bmod 3 \end{eqnarray*}$

gleichbedeutend??? Sind sie nicht: $\begin{eqnarray*} x=1 \end{eqnarray*}$ ist Lösung der zweiten Kongruenz, aber nicht der ersten. unglücklich

Die ÄQUIVALENTE (!) Aufteilung einer Kongruenz $\begin{eqnarray*} ax\equiv b\bmod \left(m_1\cdot m_2\right) \end{eqnarray*}$ als System zweier Kongruenzen

$\begin{eqnarray*} ax\equiv b\bmod m_1 \end{eqnarray*}$
$\begin{eqnarray*} ax\equiv b\bmod m_2 \end{eqnarray*}$

ist nur für TEILERFREMDE (!) Module $\begin{eqnarray*} m_1,m_2 \end{eqnarray*}$ statthaft. Du wendest das hingegen auf $\begin{eqnarray*} m_1=3,m_2=3 \end{eqnarray*}$ an, die selbstverständlich nicht teilerfremd sind. unglücklich

26.07.2021, 19:35

MMchen60

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Du wendest das hingegen auf $\begin{eqnarray*} m_1=3,m_2=3 \end{eqnarray*}$ an, die selbstverständlich nicht teilerfremd sind. unglücklich

OK. kapiert. Dann verstehe ich allerdings nicht, wieso du dann die beiden Zeilen addiert hast, da doch die eine Zeile mod 3 war und die andere mod 3^2.

26.07.2021, 21:17

HAL 9000

Auf diesen Beitrag antworten »

Hmm, mal sehen wie kleinteilig ich das noch erläutern muss...

Aus $\begin{eqnarray*} a\equiv b\bmod m \end{eqnarray*}$ folgt auch $\begin{eqnarray*} a\equiv b\bmod t \end{eqnarray*}$ für JEDEN Teiler $\begin{eqnarray*} t \end{eqnarray*}$ von $\begin{eqnarray*} m \end{eqnarray*}$ , genau das sollte mein obiges "Die ersten beiden Kongruenzen modulo 3 betrachtet" bedeuten:

Denn Modul $\begin{eqnarray*} m=15 \end{eqnarray*}$ hat Teiler $\begin{eqnarray*} t=3 \end{eqnarray*}$ (erste Kongruenz), und genauso hat Modul $\begin{eqnarray*} m=9 \end{eqnarray*}$ auch Teiler $\begin{eqnarray*} t=3 \end{eqnarray*}$ (zweite Kongruenz).

Hierbei geht es nicht um äquivalente Umformung der Kongruenzen, sondern lediglich um Implikationen - was ja zur Generierung des beabsichtigten Widerspruchs vollkommen ausreicht.

Neue Frage »

Antworten »

Lösung eines Kongruenzsystems (chinesischer Restsatz)

Verwandte Themen