Quadrat. Reste (Zahlenlehre). 124 Quadrat. Reste (Zahlenlehre). 
Weise erfüllt ja eine Zahl «, die kleiner 
als t ist, schon die Congruenz; 
(a^Elmodp. 
Offenbar ist dies auch der Fall, wenn 
s und t einen gemeinschaftlichen Factor 
haben. 
Sei in der That s — s'ci, t = t'if, und 
cT der grösste gemeinschaftliche Factor 
von s und t, so ist auch; 
a *=(«)* E1 modp, 
also u — t' zu setzen. 
Einen kleinern Werth von u gieht es 
aber nicht. Denn sei r ein solcher, so 
wäre 
a ST E 1 modp 
und st in der Reihe der Zahlen t, 2t, 
31 u. s. w. enthalten, es wäre also: 
st — s'ö't — hdt', 
wo h eine ganze Zahl ist, oder 
s't — hl'. 
Da s' und l' keinen Factor gemein ha 
ben, so ist diese Gleichung nur zu er 
füllen, wenn t gleich t' oder gleich einem 
Vielfachen dieser Zahl ist, was gegen 
die Annahme ist. 
Es gehört also a zum Modul t', und 
wenn t und s keinen Factor gemein ha 
ben zum Modul t. Wenn es also eine 
Zahl gibt, die zum Exponenten t ge 
hört, wo t ein Factor von p—1 ist, so 
gibt es dann soviel, als es relative 
Primzahlen zu t gibt, die kleiner als t 
sind, oder y(t). 
Es lässt sich aber beweisen, dass es 
zu jedem Factor t von p—1 auch wirk 
lich zugehörige Zahlen gibt. Denn neh 
men wir alle Factoren t von p—1, so 
können zu jedem nur entweder 7 (t) oder 
Null Zahlen gehören. Die Gesammtzahl 
aller dieser Zahlen stellt aber natürlich 
alle nach Modul p incongruenten Zahlen 
vor und muss daher gleich p sein. Es 
lässt sich nun beweisen, dass wenn 
t 2 • • • l s die Factoren von p—1 sind, 
man immer hat 
?(*.)+»(»«)+ * * • +»(*.)=?*) 
*) Den Beweis dieses Satzes geben wir 
nach Dirichlet. 
Von den Zahlen 
1, 2, 3 • • • p 
haben offenbar nur die folgenden 
t, 2t, Bt ... ~ t t 
den Factor t mit p gemein. Dies ist 
aber nur bei denjenigen der grösste 
und folgtich kann zu keinem Factor die 
Anzahl Null gehören. 
Hieraus ergiebt sich also der Satz: 
„Zu jedem Factor l von p — 1 als 
Exponenten gehören immer 7 (i) Zahlen.“ 
Jede zu t gehörige Zahl x nennen wir 
nunmehr eine primitive Wurzel der Con 
gruenz : 
t 
x El modp 
und unser Satz sagt somit, dass diese 
Congruenz 7 (<) primitive Wurzeln habe. 
Die Congruenz 
x V 1 El modp 
hat also 7 (p—1) primitive Wurzeln, und 
diese werden vorzugsweise primitive Wur 
zeln der Zahl p genannt. 
8) Beispiel. Sei z. B. die Primzahl 
p = 23 gegeben, so ist p—1=22 — 2 «11. 
Die Factoren von p — 1 sind also: 
*i = 1, <2=2, < s = 11, <,=22. 
Die Congruenz 
x * 1 El mod23 
hat natürlich nur die primitive Wurzel 
a = l. 
gemeinschaftliche Factor, den sie mit 
p haben, bei welchen der erste Factor 
1, 2, 3 • . • 2- 
V 
mit — relativ einfach ist, und die An- 
t 
# 
zahl dieser Zahlen ist y\ 
man nun für t alle Theiler 
<n <2 • • • t s 
von p, so drückt die Summe 
Setzt 
»(#+»(£)+»(£)+•• •■*•(£) 
aus, wie viel Zahlen der Reihe einen 
der grössten gemeinschaftlichen Facto- 
p p p ... 
ren -j-, f ’ ‘ ‘ 1 mit P gemein haben. 
Schliesslich aber hat doch jede Zahl 
einen dieser Factoren (i = l und t = p 
eingesehlossen) und somit ist diese 
Summe gleich der Anzahl aller Zahlen 
der Reihe, d. h. gleich p. Da jedem 
P 
t nun ein — entspricht, so kann man 
P p 
— =<\, —= t' 2 • • • setzen, und hat 
<1 <2 
also: 
P = '/(<i) + 7(< 2 )+ * ’ * +</(<*). 
wie oben gesagt wurde.