Lösbarkeit Simultaner Kongruenzen Beweis

Question

Seien a₁, a₂ ∈ ℤ und n₁,n₂ ∈ ℤ>0. Zeigen Sie: Die simultanen Kongruenzen

x ≡ a₁ mod n₁
x ≡ a₂ mod n₂

sind genau dann lösbar, wenn
a₁ − a₂ ≡ 0 mod ggT( n₁, n₂).

Die Lösung ist eindeutig modulo dem kgV (n₁, n₂).

Answer 1

Hallo

 schreibe x=k*n1+a1 und x=l*n2+a2

 subtrahiere die 2 Gleichungen oder setze sie gleich , bring a1-a2 auf eine Seite

Gruß lul

Comments

Vielen Dank schonmal! Kannst du vlt noch kurz erläutern wie man auf die beiden Gleichungen kommt?

---

Ich habe dann folgendes stehen: a1-a2 = l*n1 - k*n2

Die rechte Seite entspricht dem ggT(n1,n2), sehe ich das richtig?

---

Hallo

nein, du musst begründen, warum die rechte Seite 0 mod ggT(n1,n2) sein muss.

und zur ersten frage, was bedeutet den x=a mod n

Gruß lul

---

Wie konnte ich nur nicht erkennen was das für Gleichungen sind...

Kannst du bitte kurz erklären, warum die rechte Seite 0 mod ggT(n1,n2) sein muss? Ich komme da irgendwie nicht drauf.

LG

---

Hallo

 ist die Seite durch den ggT(n1,n2) teilbar?

---

Hi,

wie zeigst du denn die andere Richtung?

LG