Aufgabe:
Finde das kleinste \( x \) für welches gilt:
\( x \; \mod \; 33 = 6 \) und \( x \; \mod \;21 = 9 \)
Problem/Ansatz:
Da \( ggT(33, 21) = 3 \neq 1 \) lässt sich das ganze ja nicht direkt über den chinesischer Restsatz ausrechnen. Daher war mein gedanken das weiter aufzuteilen.
$$x\; \mod\;33 = 6 \rightarrow \begin{matrix} 1) x \mod 3 \equiv 0\\ 2) x \mod 11 \equiv 6 \end{matrix} \quad \quad \quad x\; \mod\;21= 6 \rightarrow \begin{matrix} 3) x \mod 3 \equiv 1\\ 4) x \mod 7 \equiv 1 \end{matrix} $$
$$ \begin{matrix} x \; \mod \; 3 \equiv 0 &|& * & &|& 0 &|& 0\\ \hline x \; \mod \; 11 \equiv 6 &|& (3\cdot3\cdot7)x\; \mod\;11 = 1 &= 8x\; \mod\;11 &|& x\equiv 7 &|& 6(3\cdot3\cdot7)7 \equiv 567\; \mod \; (3 \cdot 11 \cdot 3 \cdot 7) \\ \hline x \; \mod \; 3 \equiv 1 &|& (3\cdot11\cdot7)x\;mod\;3 = 1&= 0x\; \mod\;3&|& ** &|& \text{keine Lösung} \\ \hline x \; \mod \; 7 \equiv 1 &|& (3\cdot11\cdot3)x\; \mod\;7 = 1&= 1x\; \mod \;7 &|& x\equiv 1 &|& 7(3\cdot11\cdot3)1 = 693 \equiv 0 \; \mod \; (3\cdot11\cdot3\cdot7) \\ &&&&&&& \sum = 567 \end{matrix} $$
Problem #1:
Die Gleichung von 1) ergibt 0, somit würde man am Ende die Inversion, und sonstige komponente \cdot 0 Rechnen = 0
Problem #2:
Die Gleichung 3) hat keine Lösung
567 mod 33 ist zufälligerweise 6, aber 567 mod 21 geht nicht auf
Wie würde man solch eine Aufgabe richtig lösen?
Ich bin bspw. so auf die Lösung gekommen, aber habe 99.9% nur rumgeraten bis ich auf ein ergebnis kam..:
$$x\; mod\;33 = 6 \rightarrow x = 6\;+\;33a\text{ und } x\;mod\;21 = 9 \rightarrow x = 9\;+\;21b$$
$$\Rightarrow a = \frac{7b+1}{11} \rightarrow b = 3 \rightarrow a = 2$$
$$x = 9+21b = 72 \rightarrow x\; mod\;33 = 72 = 6 \text{ und } x\;mod\;21 = 72 = 9$$
