Die Elemente der Zahlentheorie / dargestellt von Paul Bachmann.

64 Zweiter Abschnitt
q'x - in' (modo n').
Da aber in dieser nun q', n' relativ prim sind, so hat sie,
dem soeben Bewiesenen zufolge, unendlich viel Lösungen,
welche durch eine Congruenz von der Form
(25) x - r (mod. n')
gegeben werden; indessen sind diese, zwar für den Modulus
n' congruenten Lösungen doch nicht auch alle (mod. n)
congruent, zerfallen vielmehr in d verschiedene Restclassen
(mod. n) und repräsentiren daher auch d verschiedene
Wurzeln der gegebenen Congruenz. Denn die Beziehung (25) sagt. dasselbe wie die Gleichung
x = r + n'z,
wenn für z alle ganzen Zahlen gesetzt werden; diese aber
nimmt, wenn S in der Form dy + e gedacht wird, in welche
es jederzeit gesetzt werden kann, während e eine der Zahlen
0, 1, 2,... d - bezeichnet, die Gestalt an:
x (r + nz'c) + ny
oder
x _ r + n'e (mod. n),
und stellt, entsprechend den möglichen Werthen von e, die
d (mod. n) incongruenten Wurzeln der Congruenz (22) vor,
nämlich:
(26) x -r, x r+ n x r+2 n',.... xr (d-i)n'
(mrod. n).
Zum Beispiel, wenn die Congruenz vorliegt:
30x - 42 (mod. 108),
so ist d = 6; da m =42 durch 6 theilbar ist, ist die Congruenz lösbar und gleichbedeutend mit dieser:
5x _ 7 (mod. 18).
Als ihre Wurzel findet man leicht
x _ 5 (mod. 18),
und hieraus folgen als Wurzeln der gegebenen Congruenz:
x - 5, 23, 41, 59, 77, 95 (mod. 108).