Quadrat. Reste (Zahlenlehre). 122 Quadrat. Reste (Zahlenlehre). 
Quadr. 
That durch Galois geschehen. Es ist 
über diesen Gegenstand der Artikel Zahl 
nachzuschen. 
6) Die Potenzreste. 
Seien k und a relative Primzahlen, 
ohne dass vorausgesetzt wird, dass k 
auch eine absolute Primzahl sei; es kann 
dann weder 1 noch a, noch « 2 , noch 
a 3 ... durch k theilbar sein und von der 
Reihe 
er 
a‘, a- 
ist also jedenfalls keine congruent Null 
nach Modul k. 
Es können aber gewisse Glieder der 
Reihe schon vorhergegangenen congruent 
sein. 
Nehmen wir daher an, es sei in der 
That 
h _ i 
a —a mod Ar 
7) Wir bezeichnen jetzt mit </(w) die 
Anzahl der Zahlen, welche zu m relativ 
einfach, und kleiner als m sind. 
Ist z. B. ?rt = 9, so sind aus der Reihe 
1, 2, 3, 4, 5, 6, 7, 8 
die 6 Zahlen 
1, 2, 4, 5, 7, 8 
mit 9 relativ einfach, also y(9) = 6. 
lieber den allgemeinen Ausdruck der 
Grösse tf (m) sehe man den Artikel Zahl. 
Eür diese Betrachtungen ist derselbe 
nicht nothwendig. Jedoch bemerken wir, 
dass wenn m eine Primzahl ist, offenbar 
— 1 
ist, da alle Zahlen der Reihe 
1, 2 
und l sei grösser als h, dann ist auch: 
d. h. 
/ h 
a — a = 0modA , ) 
(« — l))a —0 modAr 
und da a nicht congruent Null sein 
kann, jedenfalls: 
a h E 1 mod k. 
Setzen wir also l—h=t, so sehen wir, 
dass „wenn a die erste Zahl der Po 
tenzreihe von a ist, die mit n° oder 1 
congruent, alle vorhergehenden Werthe 
der Reihe 
i—i 
a°, a l , a* • • • a 
einander incongruent sind.“ 
Denn wären die Potenzen a , a , wo 
s und s' kleiner als t sind, congruent, 
so müsste ja 
.9—S * 
a El mod k 
sein, was der Voraussetzung widerspricht. 
„Die Potenzreihe 
,.o —1 
heisst Restperiode,“ und man sagt, „dass 
die Zahl a in Bezug auf Modul k zum 
Exponenten t gehöre.“ 
Natürlich kann man für jede Potenz 
dieser Reihe auch ihren Rest nehmen. 
zu m dann relativ einfach sind. 
Betrachten wir nun den Ausdruck ax, 
wo a zu einer gegebenen Zahl k relativ 
einfach sein soll. 
Setzt man nun für x alle Zahlen von 
0 bis Ar—1, so ergeben sich, wie aus 
dem im Abschnitt 2) Gesagten augen 
blicklich folgt, nur incongruente Werthe 
für den Ausdruck ax. Die Reste davon 
nach Modul k sind also wieder die Zah 
len 0 bis k — 1, jedoch natürlich in an 
drer Ordnung, als die der natüxdichen 
Zahlen 0 bis k—1 ist. 
Sei nun aber x' ein Werth von x, 
der kleiner als k und zu Ar relativ ein 
fach ist, und sei ferner r der Rest von 
war' nach Modul Ar, so ist auch r relativ 
einfach zu k; wie wir eben gesehen, 
entspricht aber jedem x' ein andrer 
Werth v. Da es nun >iQt) Werthe von 
x' gibt, welche die Bedingungen, die 
wir eben aufgestelit haben, erfüllen, so 
muss es auch y (Ar) Werthe von r ge 
ben. Diese Werthe werden also offen 
bar dieselben als die von x', nur in an 
drer Ordnung, sein (da es nur y(Ar) sol 
cher Werthe überhaupt gibt). 
Ist also 
y(Ar) = A 
und 
M. 
k 
sind die Werthe von x f , so sind die 
Zahlen 
au., au., • • • au. 
Beispiel. Suchen wir die Restpe 
riode von 7 nach Modul 13. 
Sie ist: 
7° El, 7 l e7, 7 2 E10, 7 3 e5, 7*e9, 
7 5 Eil, 7 e =12, 7 7 E6, 7 s e3, 7 9 e8, 
7 1 o E4, 7 11 E2, 7 12 El. 
Es kehrt von nun an die Periode wie 
der, da 7 12 E 7° ist. 
immer je einem Werthe der Reihe 
u,, M., 
congruent, also wenn man das Product 
bildet: 
u^ -- u t m , • • • u^ mod k 
oder 
Dieser r 
verallge 
Beis 
also 
ist. 
Ist p 
gesehen 
Dieser 
verallgei 
nach se 
Satz gei 
Anm 
F ermat’ 
Congrue 
für den 
und wen 
1-2 + 1 
Dieser le 
ist, das 
theilbar 
7) Wer 
nicht 2 c 
Modul p 
ist, so s, 
zum Exp 
Es mö 
und besc 
Zahlen z 
gebenen 
„Es mi 
Zahlen m< 
p~ 1 sein 
Denn 
kann dure 
x~t erfüll 
sie auch 
erfüllt. Ab 
denn hätte 
nicht in