§. 13. Theilbarkeit der Zahlen. 
95 
gemeinschaftliche Divisor von m und k bezeichnet wird. Denn nach der 
Voraussetzung ist m(a — b) durch fc theilbar, also auch ^(a — b) durch 
??? lc 1c 
^ theilbar; nun ist ^ prim zu folglich a — b durch ^ theilbar (4). 
Aus 27 = 12, mod 5 schließt man 9 = 4, mod 5 
Aus 120 = 84, mod 18 schließt man 10 = 7, mod 3 
19. Alle Zahlen werden nach dem Modul k in L Classen so 
getheilt, daß die Zahlen einer Classe mit 0, die Zahlen einer andern 
Classe mit 1, u. s. w., die Zahlen der letzten Classe mit Tc — 1 nach 
dem Modul k congruiren. Zahlen einer Classe sind congruent, Zahlen 
verschiedener Classen sind incongruent nach dem angenommenen Modul 
(17). Wählt man ans jeder Classe eine Zahl nach Belieben ans, so 
hat man ein vollständiges System nach dem Modul k incon- 
gruenter Zahlen, wie es z. B. je k folgende Zahlen c, c -j- 1, 
c —J— 2, . . , o —J— k — 1 bilden. 
Wenn die Zahlen x lf x 2f . ., x k nach dem Modul k incongruent 
sind und b prim zu k, so bilden die Zahlen a -s- bx lf a -j- bx 2 , . 
a + bx k wiederum ein vollständiges System incongruenter Zahlen. 
Wären a + bx v und a -f- bx 2 congruent nach dem Modul k, so wäre 
ihre Differenz b{x x — x 2 ) durch k theilbar; nun ist b prim zu k, also 
wäre x x — x 2 durch k theilbar (4), mithin x v = x lt mod k gegen 
die Voraussetzung. 
Wenn 6 ein Divisor von k ist, so giebt es gv(^) Zahlen der 
Reihe 1, 2, . ., k r für welche ö der größte Divisor ist, den sie mit k 
gemein haben (16). Also giebt es Classen, die solche Zahlen 
enthalten, daß 6 der größte Divisor ist, welchen sie mit k gemein haben. 
Insbesondere giebt es cp(k) Classen, deren Zahlen prim zu k sind. 
20. Die Reste von Producten oder Potenzen werden am ein 
fachsten aus den Resten ihrer Factoren berechnet. Wenn a und d nach 
dem Modul k die Reste r und r haben, so hat ad nach dem Modul 
k denselben Rest als rr d. h. ad = rr, mod k (18). Und wenn a (e 
den Rest s hat, so hat a K+1 denselben Rest als rs. Z. B. Nach dem 
Modul 13 haben 217 und 57 die Reste 9 und 5, folglich 217 . 57 
= 9.5=6, und 57 2 = 25 = — 1. 
Nach dem Modul 2 ist a tt = a, weil beide den Rest 0 oder 1 
haben, je nachdem a gerade oder ungerade ist.