H. 13. Theilbarkeit der Zahlen.

95

Wenn S ein Divisor von 1- ist, so giebt es Zahlen der

Reihe 1, 2, . . , L, für welche ü der größte Divisor ist, den sie mit Lgemein haben (16). Also giebt es Classen, die solche Zahlen ent-halten, daß ä der größte Divisor ist, welchen sie mit L gemein haben.Insbesondere giebt es y>(L) Classen, deren Zahlen prim zu L sind.

2tt Die Reste von Prodncten oder Potenzen werden am einfach-sten aus den Resten ihrer Facloren berechnet. Wenn « und «' nachdem Modul L die Reste r- und haben, so hat nach dem Modul/e denselben Rest als d. h. ^ nwü 1: (18). Und wenn ««den Rest § hat, so hat denselben Rest als Z. B. Nach demModul 13 haben 217 und 57 die Reste 9 und 5, folglich ist 2!7. 57^9.5^ 6, und 57- ^ 25 ^ — 1.

Nach dem Modul 2 ist <,.« ^ a, weil beide den Rest 9 oder Ihaben, je nachdem » gerade oder ungerade ist.

Nach dem Modul 5 sind alle Zahlen congruent mit einer der Zah-len 0, I, — 1,2,- 2. Nach demselben Modul sind also alle Quadratecongruent mit einer der Zahlen 9, 1,-1. Daher ist entweder a odera- - 1 oder 1 durch 5 theilbar, mithin ist «(«"- — 1)(«? 1)^ g durch 5 theilbar, d. h. a'° ^ a, moä 5 und moä 2, folg-

lich auch mocl 19. Die 5ten Potenzen haben dieselben Einer als dieZahlen.

Nach dem Modul 13 sind die Potenzen 57, 57Z 5D',. . der Reihenach congruent mit 5, — 1, — 5, l in periodischer Wiederkehr. Nachdem Modul 11 sind 9, 9?, 9^, . . der Reihe nach congruent mit - 2,4, 3, 5, 1; nach dem Modul 5 sind dieselben Potenzen der Reihenach congruent mit — 1, 1. Nach dem Modul 12 sind 15, 15-, 15^,. . der Reihe nach congruent mit 3, — 6, — 3, 6.

21 . Wenn der Modul eine Primzahl -- und der Dignand » durchnicht theilbar ist, so bilden die Reste der Potenzen a, . . Pe-

rioden von höchstens — 1 Gliedern, indem ap-> ^ I, «r ^ n, . .,moä ^-*). Wenn der Modul eine zusammengesetzte Zahl k und « primzu L ist, so bilden die Reste von «, a-, a^, . . Perioden von höchstens

d. i. so viel Gliedern, als Zahlen der Reihe 1, 2, . . , /e primzu b sind, indem ^ 1, moä b.

Mermat's Lcbrsatz (1640). Die Ausdehnung dieses Satzes auf zusammen-gesetzte Moduln hat Euter gefunden tilov. Ooiuiu. kotro^. 8. p. 74. Vergl. GaußOlKg. uritlun. 50. Der obige einfache Beweis ist von Di richtet gegeben wordenEreile I. 3 p. 390. und Zahlentyevrie K. 19.