•aMKflHlB 
Reste (Zahlenlehre). 
1 modp, 
, m+1 ) 
2 ~ 
Zahl war. 
v(P*) 
kann aber of- 
nt +1 oder —1 nach 
m nach dem Fermat- 
mod p , 
Werthe +1 oder —1 
Congruenz (siehe den 
nur 2 Auflösungen 
= f modp , 
Werthe +1 oder — 1 
ter auch 
— 1 modp 
eine der Congruenz 
El modp . 
der letztem aber sind, 
iahen, mit denen von 
El modp 
de Auflösung von 
-1 i 
— 1 modp 
E 1 modp”* 
ngruent sein. D. h. es ist 
m 
%+vp . 
Quadrat. Reste (Zahlenlehre). 151 Quadrat. Reste (Zahlenlehre). 
Das positive u kann nur die Werthe 
0, 1, 2, . . . p-1 
m-\-1 
haben, da x kleiner als p sein soll. 
Zu jedem Werth von a ergeben sich 
also höchstens p Werthe von x, und 
m , y (p m ) 
falls für p - ~ 
sich nicht mehr als 
ergeben, kann diese Zahl nicht grösser 
py(p™_) 
2 
als 
'l(r m+i ) 
Für in — 1 ist nun die Anzahl der 
Lösungen von 
x'JPE1 modp oder von x^ ^ = 1 modp 
p — 1 
gleich -- , nämlich jeder quadratische 
Rest ist eine Lösung. Es folgt also durch 
vollkommene Induction, dass auch für 
p m die Anzahl der Lösungen nicht grös 
ser als sein kann, dass also keine 
Nichtreste sich darunter befinden. 
Es ist also für alle quadratische Reste 
a von A: 
a*'f _ p mo q A 
und für alle Nichtreste b von A: 
mo d A 
zu setzen. 
20) Der verallgemeinerte Wil- 
s onsche Satz. 
Der Wilsonsche Satz lehrt, dass das 
Product 1*2*3 • • • (p—1) immer con- 
gruent — 1 nach Modul p ist. wenn p 
eine Primzahl bedeutet. Umgekehrt, ist 
l*2*3***(p—1)E —1 modp, so muss p 
eine Primzahl sein. Denn wäre 1 • 2 • • • 
(p—1)+1 durch p theilbar, p aber eine 
zusammengesetzte Zahl, so müsste sie 
einen in 1 • 2 • • • (p — 1) enthaltenen 
Factor haben, also 1 durch denselben 
theilbar sein, was unmöglich ist. 
Es ist aber dieser Satz einer Verall 
gemeinerung fähig, welche lautet: 
„Das Product aller Zahlen, welche 
kleiner als eine gegebene A und zu 
dieser relativ einfach sind, ist entweder 
congruent +1 oder congruent —1 nach 
Modul A.“ 
Der Beweis, der sich an die Theorie 
der quadratischen Reste anschliesst, mag 
noch diesen Artikel beendigen. 
Es sei 
an, «, 
= 2‘ P P t ‘Pj 1 * **, 
wo p, a, «j ganze positive Zahlen, 
(u kann auch Null sein) p, p lf p a ... 
ungrade Primzahlen anzeigen. 
Bezeichnen wir unter k irgend einen 
quadratischen Nichtrest von einer der 
ungraden Primzahlen, etwa von p, so 
kann man die unbestimmten Gleichungen: 
a~pn+k = 2s(p l p 2 p 3 ...)+! 
immer auflösen, und die sich erge 
hende Zahl a wird: 1) zu pp t p 2 • • *, 
d, h, zu A relativ einfach, 2) ungrade, 
3) Nichtrest von p, also auch von A 
sein. 
Wir bezeichnen jetzt mit 
h ln ln ls • • • 
diejenigen Zahlen, welche zu A relativ 
einfach und kleiner als A sind. Die 
Anzahl derselben gibt also der Ausdruck 
y(A) an. 
Es ist dann die Congruenz 
l v x E (i mod A 
immer lösbar durch eine Zahl x, die 
kleiner als A und zu A relativ einfach 
sein wird, also durch eine andere aus 
der Reihe der l. 
Löst man nun auch die Congruenz 
¿ 2 pE«mod A 
auf, wo l 2 weder mit l, noch mit x zu 
sammenfällt, so wird y auch in die Reihe 
der l fallen, aber von l t , l 2 und von x 
verschieden sein. Denn wäre y = so 
wäre 2 
l 2 E« mod A, 
also a ein quadratischer Rest von A, 
was gegen die Annahme ist. 
Wäre y = l t , so müsste 
LL'EamoiA 
und da 
ist, auch 
l)X = a mod A 
l t (x—l 2 ) — 0 modA 
sein, d. h. da zu fl relativ einfach 
ist, 
x — l 
was ebenfalls der Annahme widerspricht. 
Wäre endlich y~x, so wäre 
/ t .r E a, l 2 x = a, also l^ = / a , 
was ebenfalls der Annahme widerstreitet. 
Die y(A) Zahlen 
ll l\.1 *21 13 * * * 
lassen sich also in Producte von je 
zweien vereinen, deren jedes nach Mo 
dul A mit a congruent ist. Die Anzahl 
dieser Producte ist 
<M). 
; also wenn man