Quadrat, Reste (Zahlenlehre). 120 Quadrat. Reste (Zahlenlehre). 
und leicht erhält man 
s 0 — 1, also s = l+5<, 
d. h. 
® = 103+3151 
oder 
XE103 mod315. 
4) Sei jetzt wieder 
ax E b mod k; 
machen wir es aber nicht mehr zur Be 
dingung, dass auch a und k relativ ein 
fach sind. Sei dann cf der grösste ge 
meinschaftliche Factor von a und k, so 
muss, da die Gleichung 
ax—yk — b 
stattfindet, auch b den Factor d haben. 
In entgegengesetztem Falle würde die 
Congruenz unlösbar sein. 
Sei 
a — a yd, b — byd, k — kyd, 
so ist also: 
« 1 arE6 1 modÄr 1 und ayX—yky=zby. 
Ist x 0 eine Auflösung dieser Congruenz, 
so ist: 
x — x 0 -\-kyt. 
Ist y 0 der zu x 0 gehörige Werth von 
y, der sich hier durch die Gleichung 
a,x+yky = by 
ergibt, so ist offenbar: 
V-y o + «i* 
und diese Werthe in 
ax—yk— h 
eingesetzt, erfüllen, wie augenblicklich 
zu sehen, auch diese Gleichung. Alle 
Wurzeln der reducirten Congruenz sind 
also auch Wurzeln der ursprünglichen. 
Setzt man aber für t die Zahlen 0, 1, 
2 ... n—1, so erhält man Werthe für 
x, die zwar in Bezug auf Modul ky alle 
congruent also nur eine Wurzel der Con 
gruenz 
UyX^by modA-j 
sind; aber diese Werthe sind zum Theil in 
Bezug auf Modul k incongruent, und 
somit hat die ursprüngliche Congruenz 
mehrere Wurzeln. Die Anzahl derselben 
ist leicht zu bestimmen. Es war 
Von den Zahlen nun: 
o - H* 
u ’ d' d’ 
sind nicht 2 in Bezug auf Modul k con- 
• „ 
gruent, dagegen ist — wieder mit 0 con 
gruent in Bezug auf denselben Modul. 
Die Anzahl dieser incongruenten Wurzeln 
ist also d. D. h. 
„Jede Congruenz von der Gestalt 
ax = bmodk 
hat entweder gar keine Wurzel, wenn 
der grösste gemeinschaftliche Theiler d 
von a und k nicht in b enthalten ist, 
oder dWurzeln, wenn dies der Fall ist.“ 
Beispiel. Die Congruenz 
28a - E 21 mod 35 
lässt sich reduciren auf 
4a: E 3 mod 5 
und diese hat die Wurzel 
-r 0 =2, .r = 2+51. 
Die 7 incongruenten Wurzeln der gege 
benen Congruenz sind also: 
2, 7, 12, 17, 22, 27, 32. 
5) Sei jetzt die allgemeine Congruenz 
nter Ordnnng gegeben: 
. n n—1 
f{x)~ax +bx -f- • • • 
-fgic+ÄEO modp. 
Wir setzen voraus, dass p eine Prim 
zahl, und a nicht durch p theilbar ist. 
Sei « irgend eine Wurzel dieser Con 
gruenz, so ist also auch : 
re n—1 
an +o« -j- • • • -(-pa+Ä — 0 modp 
und wenn man dieselbe von der vorher 
gehenden abzieht, erhält man: 
. n n n—1 11—1. 
a(x — « ) + b(x — « ) + •••• 
y(x — «)E0 mod 
Es haben aber sämmtliche Glieder den 
Factor x—«, so dass man erhält 
/ \ x n —1 n —2 
\x — n) {ax -\-Jxx + • • • 
4- G) E 0 mod p, 
wo B • • • G ganze Zahlen sind, die sich 
leicht bestimmen lassen. 
Es kann aber diese letzte Congruenz 
nur erfüllt werden, entweder, wenn 
iE« modp, 
was die ursprüngliche Auflösung war, oder 
wenn 
n—1 n—2 
ax 4-Bx 4- • • • 4-GzrOmodjp ist. 
Ist ß eine Wurzel dieser Congruenz, so 
ist dieselbe, ganz ebenso wie oben, auf 
die Form zu bringen; 
n—2 
{x—ß) (ax +••••) EOmodp, 
welche erfüllt ist, wenn 
x E ß mod p, 
oder wenn: 
re—2 
ax 4- .... _o modp 
ist. Indem man so fortfährt, kommt 
man zuletzt auf die Congruenz ersten 
Grades 
ax-\-HEO modp, 
welche nur eine Wurzel haben kann, da 
a und p relativ einfach sind. 
Es ergiebt sich also der Satz: 
„Jede Congruenz nten Grades, wo der 
Modul eine Primzahl, und der Coefficient 
des ersten Gliedes nicht durch den Mo 
dul theilbar ist, hat höchstens n Wurzeln.“ 
Quadri 
Sin 
7 0*0 = 
wo n, £ 
sind. 1 
ist, dem 
ist, so 1 
ist. 
Dei 
Es hatte 
die Wui 
gruenz 
oder: 
mithin \ 
( 
durch di 
erfüllt. 
Ist nui 
by-l 
nicht cor 
hat man 
einem ge 
die denn 
wir gesel 
womit ur 
„Es ist 
für jeden 
Glieder n 
Noch j 
Satz. 
„Sei 
eine Con 
Primzahl 
wo der C 
ff y (x) der 
sein muss 
Es hat 1