44 (A. 14)
PAUL STACHEL:
dem Eingang (2cr„ + 2n) die Primteiler der Zahl ±2wV + 2u. Jetzt
sei 2n —2a durch p teilbar. Um festzustellen, welche der
Zahlen 2a±2zuV = 2a —2a + (±2zuj,;,+2a) den Teiler p besitzen,
hat man demnach die k + 1 Spalten mit den Eingängen (2<7„ + 2a)
aufzudecken und von den Zeilen diejenigen freizumachen, denen
die Eingänge (2 a,,) zukommen. Wenn man noch die aufgedeckten
Zeilen und Spalten aneinander schiebt, so entsteht ein Quadrat
von (k+l)^ Feldern, das für die entsprechenden Felder des Qua-
drats Q(2n„, 27z + 2n„) angibt, ob sie den Primteiler p aufweisen.
ln vielen Fällen ist es jedoch nicht nötig, das ganze Quadrat
herzustellen. Um nämlich den Beitrag zu ermitteln, den die
ersten k + 1 Zeilen des Dreiecks A(2n„, 27?. + 2<7„) zur Funktion z(p)
liefern, hat man dem Quadrat Q(2o„, 271 + 2(7,,) noch das obere
Dreieck A(2u„) hinzuzufügen und darin vermöge des großen wirk-
samen Dreiecks die Zahlen 2w„; durch ihre ungeraden Primteiler
zu ersetzen. Dann kommen von dem Quadrat nur diejenigen Zei-
ten in Betracht, die im Dreieck A(2n„) von p frei sind. Wenn
also sämtliche Zeilen dieses Dreiecks p enthalten, so genügt es,
allein die (k + l)-te Zeile zu berücksichtigen. Nur wenn sämtliche
Zeilen des Dreiecks von p frei sind, muß man das volle Quadrat
nehmen, hat dann aber mit dem Dreieck nichts mehr zu tun.
Eine weitere Vereinfachung ergibt sich daraus, daß eine Zeile,
deren Eingang mit einem der Eingänge der Spalten übereinstimmt,
notwendig den Primteiler p enthält, nämlich an der Kreuzungs-
stelle; folglich dürfen auch solche Zeilen von vornherein weg-
gelassen werden.
Der Fall, daß 2a + 2a durch p teilbar ist, läßt sich so-
fort auf den soeben betrachteten Fall, daß 2 a —2 a den Teiler p
besitzt, zurückführen, wenn man darauf verzichtet, daß 2a kleiner
als p sein soll, und für 2a alle p geraden Reste gegen 2p nimmt,
oder vielmehr diejenigen geraden Reste, die bei den Zahlen 2w^;
auftreten.
Zwischen den beiden Quadraten, die man erhält, wenn 277-2a
und wenn 2a —(2p —2a) und damit 2a + 2a durch p teilbar ist,
besteht eine einfache Beziehung. Sind nämlich im ersten Quadrat
zwei zur Hauptdiagonale symmetrische Felder, die also zu zwei
Zahlen + 2za^ + 2a gehören, frei von p, so gilt dasselbe für das
zweite Quadrat, weil hier zu denselben Feldern die zwei Zahlen
+ 2zu^,^ + 2p —2a = 2p —(+2w),; + 2a) gehören. Ist aber beim ersten
PAUL STACHEL:
dem Eingang (2cr„ + 2n) die Primteiler der Zahl ±2wV + 2u. Jetzt
sei 2n —2a durch p teilbar. Um festzustellen, welche der
Zahlen 2a±2zuV = 2a —2a + (±2zuj,;,+2a) den Teiler p besitzen,
hat man demnach die k + 1 Spalten mit den Eingängen (2<7„ + 2a)
aufzudecken und von den Zeilen diejenigen freizumachen, denen
die Eingänge (2 a,,) zukommen. Wenn man noch die aufgedeckten
Zeilen und Spalten aneinander schiebt, so entsteht ein Quadrat
von (k+l)^ Feldern, das für die entsprechenden Felder des Qua-
drats Q(2n„, 27z + 2n„) angibt, ob sie den Primteiler p aufweisen.
ln vielen Fällen ist es jedoch nicht nötig, das ganze Quadrat
herzustellen. Um nämlich den Beitrag zu ermitteln, den die
ersten k + 1 Zeilen des Dreiecks A(2n„, 27?. + 2<7„) zur Funktion z(p)
liefern, hat man dem Quadrat Q(2o„, 271 + 2(7,,) noch das obere
Dreieck A(2u„) hinzuzufügen und darin vermöge des großen wirk-
samen Dreiecks die Zahlen 2w„; durch ihre ungeraden Primteiler
zu ersetzen. Dann kommen von dem Quadrat nur diejenigen Zei-
ten in Betracht, die im Dreieck A(2n„) von p frei sind. Wenn
also sämtliche Zeilen dieses Dreiecks p enthalten, so genügt es,
allein die (k + l)-te Zeile zu berücksichtigen. Nur wenn sämtliche
Zeilen des Dreiecks von p frei sind, muß man das volle Quadrat
nehmen, hat dann aber mit dem Dreieck nichts mehr zu tun.
Eine weitere Vereinfachung ergibt sich daraus, daß eine Zeile,
deren Eingang mit einem der Eingänge der Spalten übereinstimmt,
notwendig den Primteiler p enthält, nämlich an der Kreuzungs-
stelle; folglich dürfen auch solche Zeilen von vornherein weg-
gelassen werden.
Der Fall, daß 2a + 2a durch p teilbar ist, läßt sich so-
fort auf den soeben betrachteten Fall, daß 2 a —2 a den Teiler p
besitzt, zurückführen, wenn man darauf verzichtet, daß 2a kleiner
als p sein soll, und für 2a alle p geraden Reste gegen 2p nimmt,
oder vielmehr diejenigen geraden Reste, die bei den Zahlen 2w^;
auftreten.
Zwischen den beiden Quadraten, die man erhält, wenn 277-2a
und wenn 2a —(2p —2a) und damit 2a + 2a durch p teilbar ist,
besteht eine einfache Beziehung. Sind nämlich im ersten Quadrat
zwei zur Hauptdiagonale symmetrische Felder, die also zu zwei
Zahlen + 2za^ + 2a gehören, frei von p, so gilt dasselbe für das
zweite Quadrat, weil hier zu denselben Feldern die zwei Zahlen
+ 2zu^,^ + 2p —2a = 2p —(+2w),; + 2a) gehören. Ist aber beim ersten