Kongruenzen - Modulo - in Z

Question

Aufgabe:

Seien n1 und n2 teilerfremde nat. Zahlen und z1 und z2 in Z. Zeigen Sie, dass es ein x gibt, sodass 
$$ x \equiv \left\{ \begin{array} { l l } { z _ { 1 } } & { \bmod n _ { 1 } } \\ { z _ { 2 } } & { \bmod n _ { 2 } } \end{array} \right. $$

Problem/Ansatz:

Ich hätte als Ansatz: Es sind z₁' und z₂' zu finden, sodass z₁+z₁' * n₁=z₂+z₂' * n₂. Dann ist x = z₁+z₁' * n₁ = z₂+z₂' * n₂ eine gemeinsame Lösung der Kongruenzen. 

Ich glaube hiermit bin ich aber noch nicht fertig, oder?

Answer 1

Die Verwendung von z1'  bzw. z2' als Bezeichener ist möglich, aber irgendwie unübersichtlich. Ich nehme mal lieber a und b.

Es gibt also laut Voraussetzung zwei ganze Zahlen a und b mit

x=a*n₁+z₁ und

x=b*n₂+z₂.

Differenzenbildung liefert

a*n₁-b*n₂+z₁-z₂₌0 bzw.

z₁-z₂=b*n₂-a*n₁

Es gibt nun einen Satz der besagt, das für teilerfremde ganze Zahlen n₁ und n₂ die Gleichung

r*n₁+s*n₂=1  stets ein Lösungspaar (r,s) besitzt.

Wenn man nun in dieser Gleichung statt der 1 eine 2, eine  3, eine 4 usw. hätte, wäre  (2r,2s), (3r, 3s), (4r,4s) ... ein entsprechendes Lösungspaar.

Wenn man mit  r*n₁+s*n₂ das Ergebnis 1 erzeugen kann, dann kann man mit einem entsprechenden Vielfachen auch das Ergebnis (z₁-z₂) erzeugen.