Die Elemente der Zahlentheorie / dargestellt von Paul Bachmann.

Von den Congruenzen. 65
Die Auflösung der Congruenz (22) ist im Grunde
nichts anderes, als die ganzzahlige Auflösung der unbestimmten Gleichung ersten Grades von der Form
(27) qx - ny == n.
Denn, wenn eine solche überhaupt lösbar ist, und x, y bezeichnen zwei ganze Zahlen, welche sie befriedigen, so folgt
qx = n + n^ y, d. i.
qx - m (mod. n);
und umgekehrt: ist x eine Lösung dieser Congruenz, so ist
die Differenz qx - i eine durch n theilbare ganze Zahl, d. i.
qx - m = n y, miithin sind x, y eine ganzzahlige Auflösung
der Gleichung (27). Um aber alle Auflösungen der letzteren
zu finden, bringen wir diese zunächst, wenn q, m einen grössten
gemeinsamen Theiler d haben, durch welchen dann auch m
aufgehen muss, auf die einfachere Form:
(28) q'x- n'y = n'.
Sind x = r, y =s eine Auflösung der letzteren, wie nach
dem Obigen eine solche stets existirt, so giebt die Verbindung
jener Gleichung mit der folgenden:
qr - n s == m,
die Beziehung:
q'(x-r) = '( -s),
aus welcher, weil q', n' relativ prim sind, sogleich folgt, dass
x - r durch n' theilbar, etwa gleich n'z, und folglich
y - s = q'z sein muss; mit andern Worten: alle Lösungen
jener Gleichung sind nothwendig in den Formeln enthalten:
x = - r+ n'z, y -s + q'Z;
diese geben aber auch, wie ersichtlich ist, für jeden ganzzahligen Werth des S wirklich eine Lösung. Da endlich die
Lösungen der Gleichung (27) mit denen der einfacheren
Gleichung (28) identisch sind, so findet sich das mit der
Lösung der Congruenz (22) in Einklang stehende Ergebniss:
Ist r, s eine Lösung der Gleichung (27) in ganzen
Zahlen, so finden sich alle ihre ganzzahligenLösungen,
wenn in den Formeln
Bach m ann, Die Elemenete der Zahlentheorie. 5