Simultante Kongruenz mit nicht teilerfremden modulo

Question

Aufgabe:

Man soll folgende simultante Kongruenz Lösen

$\begin{aligned} x & \equiv 3 \quad(\bmod 8) \\ x & \equiv 11 \quad(\bmod 20) \\ x & \equiv 1 \quad(\bmod 15)\end{aligned}$

Problem/Ansatz:

Das Problem besteht darin, dass die modulo nicht teilerfremd sind (ggt(8,20)=4 und ggt(20,15)=5). Jetzt gibt es ja folgenden Satz:

Für ggT(m1,m2) | (b1-b2) ist das System

x ≡ b1 (m1)

x ≡ b2 (m2)

eindeutig kgV (m1, m2) lösbar.

Ich bin mir aber noch nicht ganz sicher, wie das nun anzuwenden ist, bzw. ob ich das mit dem EEA so machen kann (x ist bei mir 400)?

Comments

Simultante ...

Vielleicht weiß es der Simulonkel...

☺

---

In der Tat ein lustiger Tippfehler ☺.

Wir meinen natürlich die Simultane Kongruenz

---

https://www.arndt-bruenner.de/mathe/scripts/chinesischerRestsatz.htm

x = 91 sagt dieser Onlinerechner auch, aber wie kommt man jetzt auf das Ergebnis (also was ist der formale Rechenweg)?

---

Mittels sukzessiver Substitution komme ich jetzt auch auf x = 91

11+10b Ξ 1 (mod 15)

---

Wie würde das aber trotzdem mit dem erwähnten Satz gehen (oder mit der Methode, welche ich zuerst ausprobiert habe)?

Answer 1

Hier ist ein möglicher Weg. Alle Inversen, die ich benutze, kannst du natürlich auch per EEA ermitteln. Solang die Zahlen nicht zu groß sind, gelingt es oft, die Inversen durch "scharf gucken" und "kleinem Einmaleins" zu bestimmen:

Erst einmal erste und dritte Kongruenz simultan per China-Dingsbums lösen:
$$M = 120 \Rightarrow x= 3\cdot \left[15\right]_8^{-1}\cdot 15 + 1\cdot \left[8\right]_{15}^{-1}\cdot 8$$

Die Inversen:

$$15 = 2\cdot 8 -1 \Rightarrow \left[15\right]_8^{-1} \equiv -1 \: (8)$$

$$2\cdot 8 = 16 = 15+1 \Rightarrow \left[8\right]_{15}^{-1} \equiv 2\: (15)$$

Inverse einsetzen und ausrechnen.

Teillösung: $\boxed{x \equiv -29 \equiv 91 \: (120) \quad (1)}$.

Nun nehmen wir die übrige Kongruenz dazu und blasen sie auf den Modul 120 auf:

$$x\equiv 11\:(20) \Leftrightarrow \boxed{6x \equiv 66 \: (120) \quad (2)}$$

$$(1) + (2)\Rightarrow \boxed{7x\equiv 157\equiv 37 \: (120)\quad (3)}$$7 ist teilerfremd mit 120. Wir brauchen also nur noch $\left[7\right]_{120}^{-1}$:

$$7\cdot 17 = 119 \equiv -1\: (120) \Rightarrow \boxed{\left[7\right]_{120}^{-1} \equiv -17\: (120) \quad (4)}$$

$$(3),(4) \Rightarrow x\equiv (-17)\cdot 37 \stackrel{720-629=91}{\equiv}\boxed{91\: (120)}$$

Comments

Danke dir - diesen Weg finde ich nämlich viel schöner als der mit der sukzessiven Substitution, welchen ich zuletzt verwendet habe.

---

@Euler7

Nur noch eine kleine Ergänzung:
Eigentlich ist man hier mit der Teillösung schon fertig. Denn die ist ja $91\:(120)$.
Da $91 =4\cdot 20 + 11 \equiv 11\: (20)$ haben wir so schon alle Lösungen.