X 
Reste (Zahlenlehre), 
Quadrat. Reste (Zahlenlehre). 149 Quadrat. Reste (Zahlenlehre). 
9+‘P 
aber t so bestimmen, 
k~0 moäp n ^~ tt 
! beliebige Zahl ist, die 
s oder höchstens gleich 
igruenz gibt nämlich: 
- t 2 p 2 “~ 0 modp«+ R/ 
f i 2 p r< E0 modp^. 
ch ein Vielfaches von 
offenbar eine ganze Zahl. 
ch sein: 
-k a ' 
— =0 mod p . 
tiv einfach zu p, also 
sonst wären gleichzeitig 
also auch k durch p 
id also auch g und “2g 
u p a . Dasselbe kann 
2 -k 
beweisen. Denn 
isdruck durch p s theil- 
i j CC + 5 
c modp 
«+s an die Stelle von 
diesen Umständen aber 
z 
-k 
■— — 0 mod p 
oraus denn folgt, dass 
mz 
, n — n f 
mod p 
und mithin dies auch 
: k modp ft 
ment von p beliebig ist 
lie Congruenz 
lk modp ft 
i, wenn deren eine vor- 
Denn ist g die eine Wurzel, so ist 
auch 
(— g) 2 = kmod p n . 
Es ist also 
x~g oder x = —g. 
Es kann aber auch nicht mehr als 2 
Wurzeln geben. Denn sei 
x 2 E k mod p a und E & mod p n , 
also: 
x 1 — g 2 = (x — g) (x + g) E0 mod p cc . 
Es ist dies aber nur möglich, wenn ent 
weder x—g oder x-\-g durch p a ganz 
theilbar ist, also wenn x E n~g ist. 
Denn wären beide Factoren x—g und 
x + g durch p theilbar, so wäre dies 
auch ihre Differenz 2g, was, wie oben 
gezeigt, unmöglich ist. 
Der Fall, wo p~ 2 ist, war hier nicht 
mit inbegriffen, und ist besonders zu 
untersuchen, k bedeutet hier eine un 
grade Zahl. 
Soll 
£c J E&mod4 
sein, so muss x 2 als ein Quadrat einer 
ungraden Zahl die Form 4r + l haben, 
und gleiches muss mit k der Fall sein. 
Es genügt dann jede ungrade Zahl 
dieser Congruenz, da es aber nur deren 
2 incongruente, nämlich 4r+l und 4r+3 
gibt, so sind immer nur 2 Wurzeln vor 
handen. 
Der Congruenz 
x* E k mod 8 
genügen dagegen alle ungraden Zahlen, 
wenn k von der Form 8r + 1 ist. Die 
Congruenz hat also 4 Wurzeln. 
In ähnlicherWeise untersucht man die 
höheren Potenzen von 2. 
Sei jetzt allgemein gegeben: 
x y ~k mod m, 
wo 
« re, cc. 
m -P Pi l P 2 1 • • • 
ist und p,Pi,p 2 ungrade Primzahlen sind, 
so zerfällt diese in die einfachen Con- 
gruenzen: 
x* E&modp f{ , x 1 Ek modp 1 r<l , 
x 2 E k modp a ft2 . . . 
Es ergeben sich für jede dieser Con- 
gruenzen als Auflösungen lineare For 
men, die sich in eine von der Gestalt: 
x~sm-\-A, A lf A i ... 
vereinen lassen. 
Ist pi die Anzahl der Primzahlen 
p,Pj,p 2 .. ., die in m enthalten sind, so 
ist 2‘ W die Anzahl dieser Formen, da 
jede Congruenz 2 Wurzeln gibt. 
Ist aber 
x 2 Ec kmoä 2m, 
so kommt eine Linearform 2w +1 hinzu; 
diese ändert in der Anzahl der Linear 
formen nichts, da ja 
x 2 E k mod 2 
auch nur 2 Wurzeln hat, jedoch bezie 
hen sie sich auf Modul 2m und es ist 
x~2sm-\-A,A l , A 2 . .. 
Anders ist es, wenn der Modul eine 
höhere Potenz von 2 enthält. 
19) Criterium für die Fälle, wo 
eine gegebene Zahl quadrati 
scher Rest oder Nichtrest einer 
zusammengesetzten Zahl ist. 
„Sei 
(f(A) = dN, k=dm, 
und cf der grösste gemeinschaftliche Fac 
tor von k und (j{A), so ist die Con 
gruenz 
k_ 
x = a mod A, 
wo a und A relativ einfach sind, nur 
möglich, wenn: 
i(£) 
a & =1 mod A 
ist.“ 
Dieser Satz ist die Erweiterung eines 
früher für den Fall gegebenen, wo A 
eine Primzahl ist. Offenbar nämlich muss 
x eine relative Primzahl zu A sein, da- 
k 
mit x —a durch A theilbar sein könne. 
Dann aber ist 
(x ) ^ E a mod A, 
d. h. da 
ist; 
k 
<f(A) 
x m< fW=a * 
und da nach dem verallgemeinerten Fer- 
mat’schen Satze 
3,7 C^) _ i mo( j A 
ist: 
70*) 
a ^ = 1 mod A. 
Für den Fall, wo k = d = 2 ist, ergibt 
sich hieraus, da <f{A) immer eine grade