0 Daumen
851 Aufrufe

Aufgabe:

Es seien nicht-teilerfremde naturliche 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:

leider weiß ich gar nicht wie ich dieses Problem lösen kann :( und bitte deshalb um Hilfe

Avatar von

1 Antwort

0 Daumen

Da auch die überaus punktsammlerisch veranlagten User diese Frage seit geraumer Zeit ignorieren, will ich für dich wenigstens einen Einstieg versuchen.

nicht-teilerfremde naturliche Zahlen  m1, m2

bedeutet, dass m1 und m2 einen ggT>1 besitzen, nennen wir diesen "g".

Damit gibt es teilerfremde natürliche Zahlen n1 und n2 mit m1=g*n1 und m2=g*n2..


x ≡ a1 (mod m1)

bedeutet: es gibt eine ganze Zahl q1 mit x=q1*m1+a1.

x ≡ a2 (mod m2)


bedeutet: es gibt eine ganze Zahl q2 mit x=q2*m2+a2

Setzt man beide Gleichungen gleich, folgt.

q1*m1+a1.=q2*m2+a2

Unter Berücksichtigung von m1=g*n1 und m2=g*n2. wird daraus

q1*g*n1+a1.=q2*g*n2+a2.

Umgestellt und g ausgeklammert:

g*(n1*q1-m2*q2)=a2-a1.

Da die linke Seite durch g teilbar ist, muss es die rechte auch sein..

.

Avatar von 55 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community