Die Elemente der Zahlentheorie / dargestellt von Paul Bachmann.

Von den Congruenzen. 47
nothwendig unendlich viel solcher Systeme; für n = 11 wiirde
man z. B. auch folgendes wählen können:
11, — 21, 24, -- 8, 4, 16, 61, -4, -36, 9, 21,
u. s. f.
2. Aus der Definition congruenter Zahlen ergeben sich
unmittelbar einige einfache Folgerungen. Zunächst ist
leicht einzusehen, dass alle Zahlen derselben Restclasse denselben grössten gemeinsamen Theiler mit
dem Modulus n haben müssen. Denn, ist mi'- (mod. n),
d. h. m' - m- = h n, so geht jeder gemeinsame Theiler von
mn, n auch in m, und jeder gemeinsame Theiler von m, n
auch in m' auf. - Ist also insbesondere eine Zahl einer
Restclasse relativ prim zu n, so sind es alle Zahlen dieser
Classe. Hieraus folgt offenbar, dass, wenn aus einem vollständigen Restsysteme (2) diejenigen Zahlen
(3) Q, 2, 3,...
ausgewählt werden, welche ohne gemeinsamen Theiler mit n
sind, diese Zahlen diejenigen Restclassen (mod. n) repräsentiren, in welche sich alle relative Primzahlen zu n in Bezug
auf den Theiler n vertheilen. Die genannten Classen heissen
die zu n relativ primen Restclassen, und das System (3),
durch welches sie repräsentirt werden, ein reducirstes Restsystem (mod. n), Die Anzahl v der Zahlen eines reducirten
Restsystems ist offenbar v - 9(n), wie daraus hervorgeht,
dass ja als das System (2) auch das System der kleinsten
positiven Reste 0,, 2,... n -- 1 gewählt werden dürfte, in
welchem p (n) relative Primzahlen zu n befindlich sind.
Zweitens bemerken wir, dass, wenn d ein Theiler von
n ist, aus der Congruenz mn' n (mod. n) auch die andere
folgt: mn'_ m (mod. cl), denn, ist m'- m theilbar durch n, so
ist's erst recht theilbar durch d.
Drittens. Wenn zwei Zahlen i, m' einander congruent
sind in Bezug auf jede der Zahlen nl, n', n",..., in Zeichen:
M' n (mod.n), s' u (hod. ),...
so ist auch
in'-^ m (mod. N),