0 Daumen
1,9k Aufrufe

Aufgabe:

Es seien nicht teilerfremde natürliche Zahlen m1, m2 ∈ N \ {1} gegeben. Für welche a1, a2 ∈ Z hat die folgende simultane Kongruenz eine Lösung?

x ≡ a1 (mod m1)

x ≡ a2 (mod m2)


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.

Avatar von

1 Antwort

+2 Daumen

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 .

Avatar von 287 k 🚀

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).

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community