Quadratische Reste (Zahlenlehre). 118 Quadratische Reste (Zahlenlehre). 
denn cs sind a — b und c — d durch h 
theilbar, d. h. 
a—b — ak, c—dzzßk, 
also 
a—ft+(c—d) = (n+ß)k, 
d. h. 
«+c—(6+d) 
durch k theilbar. 
Es ist aber auch: 
a = b+c(k, c = d+ßk, 
also 
ac — bd+yk, 
wo y eine ganze Zahl ist, folglich auch 
ac—bd durch k theilbar. 
Dieser Satz lautet in Worten: 
„Congruenzen desselben Modul kön 
nen addirt, subtrahirt und multiplicirt 
werden.“ 
Es folgt hieraus augenblicklich, dass 
man auf beiden Seiten einer Congruenz 
mit derselben ganzen Zahl addiren, sub- 
trahiren und multipliciren, d. h. sie in 
dieser Beziehung wie eine Gleichung be 
handeln darf. Denn sei 
a E b mod Ä, 
so ist jedenfalls 
c — c mod k, 
also auch 
und 
a+c — byre m °d ^ 
ac = bc modÄ. 
Seien jetzt f und k relative Primzah 
len, und 
af~ b mod k, 
so muss {a—h)f durch k theilbar sein, 
und da f den Eactor k nicht hat, so hat 
ihn a—b, es ist also auch 
a E b mod k. 
Habe aber f mit k einen Eactor gemein, 
und sei dieser gleich e (wo also e der 
grösste gemeinschaftliche Eactor von f 
und k ist), sei ferner f—ef r , k = ek', so 
ist 
af—bf— ef'(a—b) durch e/t' theilbar, 
also 
f(a—b) durch Id theilbar, 
oder, da f und k r keinen Eactor gemein 
haben, ist 
«E4 mod k', 
d. h. 
a ür b mod —. 
e 
Ein andrer wichtiger Satz ist der fol 
gende : 
„Von k auf einander folgenden Zahlen 
ist eine und immer nur eine einer gege 
benen a nach Modul k congruent.“ 
Denn es kann ja in dem Ausdruck 
a+nk, wo n eine positive oder negative 
ganze Zahl ist, n so bestimmt werden, 
dass dieser Ausdruck in eine beliebige 
gegebene Reihe von n auf einander fol- 
genhen Zahlen fällt. Dies kann aber 
auch nur auf eine Weise geschehen, da 
schon u+(n+l)Ä und a-\-(n—l)k um h 
von dem gesuchten Werthe abweichen, 
also nicht mehr in die gegebene Reihe 
fallen. Ist aber a-\-nk~ a, wo n die in 
unserer Reihe liegende entsprechende Zahl 
ist, so ist 
a = « modÄ. 
Eine solche Reihe von k Zahlen ent 
hält also nicht 2 unter einander für Mo 
dul k congruente Werthe. Sie heisst 
daher: „ein System incongruenter Zahlen 
in Bezug auf k. u 
Das kleinste positive System incon 
gruenter Zahlen ist die Zahlenreihe: 
0, 1, 2.. . . . k-1, 
das absolut kleinste System 
wenn k ungrade ist: 
k-1 h-3 
2 ’ 2 ’ ' * ‘ * 
+2,. . . . 
-1, 
k—1 
2 
dagegen, 
0) +1, 
und wenn k grade ist: 
Diejenige Zahl aus der ersten Reihe, 
welche einer gegebenen congruent ist, 
wird offenbar dasjenige sein, was wir 
oben Rest genannt haben. Diejenige 
Zahl aus der zweiten Reihe, welche einer 
gegebenen congruent ist, nennen wir 
jetzt den absolut kleinsten Rest. 
Statt dieser Reihen incongruenter Zah 
len, welche aus auf einander folgenden 
Werthen bestehen, kann man sich aber 
auch Reihen von der Gestalt: 
ax, a(a. - +l), a(a - +2) .... a(x-\-k—1) 
bilden, wo a eine beliebige, jedoch zu 
k relativ einfache Zahl ist. Denn auch 
in dieser Reihe finden sich nicht 2 con 
gruente Werthe. 
Wäre nämlich 
a(x-\-s)=: a{x-\-t) modÄ, 
so müsste auch 
rts = uimod& oder «(s — i) = 0mod k