Bestimmen Sie alle Lösungen des Restklassengleichungssystems

Question

Aufgabe:

Bestimmen Sie alle Lösungen des Restklassengleichungssystems

Um welches Restklassengleichungssystem es sich handelt, sieht man auf dem Blatt

Ich weiß jetzt nicht weiter, ich muss die Inversen vom chinesischen Restsatz bilden, aber ich kann irgendwie nicht die Inverse bilden, kann mir jemand bitte helfen:

(Auf die Lösungen von 5 modulo 14 und 12 modulo 14 kam ich darauf, weil ich in der Aufgabenstellung davor die Restklassengleichung lösen musste

Text erkannt:

\( \begin{array}{l} \text { c.) }\left\{\begin{array}{l} {[4]_{14} 0[x]_{14}=[6]_{14}} \\ {[7]_{10} 0[x]_{10}=[3]_{10}} \end{array}\right\} \\ {[7]_{10} 0[x]_{10}=[3]_{10} \quad 1 \cdot[3]_{10}} \\ \Leftrightarrow[x]_{10}=[9]_{10} \end{array} \)
da wir 2 Lsg. haben, stellen wir 2 Restrlarsengleichungen auf:
1.) \( \left\{\begin{array}{l}{[x]_{14}=[5]_{14}} \\ {[x]_{10}=[9]_{10}}\end{array}\right. \)
2.) \( \left\{\begin{array}{l}{[x]_{14}=[12]_{14}} \\ {[x]_{10}=[9]_{10}}\end{array}\right. \)
\( \begin{aligned} m= & \begin{array}{ll} 14 & 10 \\ d i & d z \end{array} \\ {\left[\frac{m}{d i}\right]_{d i}: } & {[10]_{14} } \\ & {[14]_{10}=[4]_{10} } \end{aligned} \)

Invere Elemente:

Answer 1

Aus 4x≡ 6 mod 14 folgt  x≡ 5 mod 7. Damit musst du nicht die Fälle x≡ 5 mod 14 und x≡ 12 mod 14 unterscheiden.

Aus x≡ 5 mod 7 und  x≡ 9 mod 10 (besser: x≡ -1 mod 10) folgt

x=7k+5 und x=10n-1.

7k+5 = 10n-1 ergibt

7k+6= 10n

und damit 6≡10n≡3n mod 7, was z.B. für n=2  erfüllt ist.

Mit n=2 gilt x=10·2-1=19=7k+5, woraus k=2 folgt.

x=19 ist also eine Lösung, und weitere Lösungen ergeben sich durch Addition von Vielfachen des kgV von 10 und 7, welches 70 ist.

Die Lösung ist also [19]₇₀.

Comments

Hab nix verstanden :/

---

Kann man das nicht mit dem chinesischen Restsatz lösen ? Gibt es eine andere Methode? Wie nennt man diese Methode?

Answer 2

Ich schreib mal noch eine Lösung mit dem Chinesischen Restsatz (CR) ausgehend von deinen beiden Gleichungen:
$$x\equiv_{14}12 \equiv_{14}-2,\quad x\equiv_{10}9\equiv_{10}-1$$

Für den CR brauchst du das kgV \(m=[14,10]=70\) der Module.

Für die Lösung gemäß CR brauchst du \(m/14 =5\) und \(m/10 = 7\).

Die Lösung per CR ist dann:

$$\boxed{x \equiv_{70} -2\cdot [5]_{14}^{-1}\cdot 5 -1\cdot [7]_{10}^{-1}\cdot 7}\quad (1)$$

Um Schreibarbeit zu sparen, setz ich $$z=[5]_{14}^{-1} \quad \text{und} \quad y=[7]_{10}^{-1}$$

Das sind die Inversen, die du suchst. Also zu lösen sind

$$5z\equiv_{14} 1 \quad \text{und} \quad 7y\equiv_{10}1$$

Jetzt könnte man mechanisch mit dem erweiterten Euklidischen Algorithmus losmarschieren.

Da du aber bestimmt das kleine Einmaleins kennst, siehst du sofort:
$$ 5\cdot 3 = 14+1 \quad \text{und}\quad 7\cdot 3 =21 = 2\cdot 10 + 1$$

Damit hast du $$z\equiv_{14}3 \quad \text{und}\quad y\equiv_{10}3$$

Das setzt du in (1) ein und bist fertig:

$$x\equiv_{70}=-2\cdot 3\cdot 5 - 3\cdot 7 \equiv_{70} -51\equiv_{70} 19 $$Fertig.

p.s.:

Du könntest übrigens gleich zu Beginn die erste Gleichung (einschließlich Modul) durch 2 teilen:$$ 4x\equiv_{14}6 \Leftrightarrow 2x\equiv_{7}3$$Damit hättest du gleich von Anfang an die kleineren Reste modulo 7.