Simultane Kongruenz ohne Inverse?

Question

wie bestimmt man Simultane Kongruenz falls es keine Inverse (nicht teilerfremd) gibt?

x mod 33 = 6

x mod 21 = 9

ggT(33,21) = 3 => also kann ich ja keine Inverse bestimmen, welche ich für den Chinesischen Restesatz bräuchte.

kgV(33,21) = 231

Wie gehe ich nun vor?

Comments

Wenn x = r mod a*b, dann ist x = r mod a und x = r mod b. Denn x ist von der Form

x=(a*b)*q + r

---

@EmNero: gibt es irgendwas spezielles was ich googeln kann um mich bei solch einer art von simultanen gleichung einzulesen?

Answer 1

x mod 33 = 6 --> x = 6 + 33a
x mod 21 = 9 → x = 9 + 21b

Da x jetzt gleich sein soll

6 + 33a = 9 + 21b
33a - 21b = 3 → a = 2 + 7k ; b = 3 + 11k

x = 6 + 33(2 + 7k) = 72 + 231·k

Comments

Sorry, aber wie kommst du auf a = 2 + 7k und b = 3 + 11k?

---

Okay, verstehe, erweiterter euklidischer Algorithmus...