Für welche a hat die simultane Kongruenz eine Lösung

Question

Aufgabe:

Es seien nicht teilerfremde natürliche Zahlen m₁, m₂ ∈ N \ {1} gegeben. Für welche a₁, a₂ ∈ Z hat die folgende simultane Kongruenz eine Lösung?

x ≡ a₁ (mod m₁)

x ≡ a₂ (mod m₂)

Problem/Ansatz:

Das ist mir irgendwie alles zu allgemein gehalten. weder a, x noch m sind definiert. Die CRS gilt, wenn die entsprechenden Module teilerfremd sind. Ich weiß z.B. dass für

x ≡ 4 (mod 6)

x ≡ 2 (mod 8)

die Gleichung für x = 10 gelten würde.

Aber ich kann ja jetzt schlecht alle möglichen Kongruenzen der Welt auflisten, da reicht mein Papier nicht für aus.

Ein anderer Ansätz wäre, allgemein zu zeigen, dass das Kongruenzsystem nur für teilerfremde Module geht. Aber die Module werden hier ja als m definiert, und es ist in der Aufgabe nach a1 und a2 gefragt.

Answer 1

x ≡ a1 (mod m1)    und    x ≡ a2 (mod m2)

bedeutet ja, es gibt h und k aus Z mit

x-a1 = h*m1    und    x-a2 = k*m2

diese beiden Gleichungen voreinander subtrahiert gibt

a2-a1 = hm1 + km2

und nach dem Lemma von Bezout gilt das

genau dann, wenn   |a2-a1 | = ggT(m1,m2).

Wie in deinem Beispiel auch deutlich wird

ggT(6,8)=2 = 4-2 .

Comments

Vielen Dank für die einleuchtende Darstellung.

---

Aber wenn ich zB. diese gleichung habe (x = 2):

x  ≡ 5 (mod 3)

x ≡ 11 (mod 9)

Ist ggT(3, 9) nicht 3, sondern 11-5 = 6...

Wie kann ich das verstehen, stimmt der beweis trotzdem?

---

Der letzte Schluss von mir (mit dem genau dann) war wohl etwas flott.

Lemma von Bezout sagt ja

Für  ggT(m1,m2). gibt es jedenfalls eine Darstellung

der Art  hm1 + km2.

Für jedes Vielfache davon aber natürlich auch; denn

aus   ggT(m1,m2). =  hm1 + km2.

folgt ja    n* ggT(m1,m2). =  n*hm1 + n*km2..

Also ist die richtige Antwort wohl:

|a2-a1 | ist ein Vielfaches von  ggT(m1,m2).