Zahlentheorie, von Adrien Marie Legendre. Nach 3 aufl. ins deutsche übertragen von H. Maser.

~ 11. Bestimmung c. Anzahl d. Glieder e. arithm. Progr., welche u. s. w. 91
A k + C'
der Gleichung k + C e genügen, so dafs man ferner k7 = —
erhält.
Vereinigt man nun alle Glieder E( -n —) mit Rücksicht auf
die ihnen zukommenden Zeichen, so wird ihre Summe dargestellt
durch - P', wo -Pw ' ) die Anzahl der Glieder bedeutet, welche
von der Progression A - C', 2A - C',... n'A - C' übrigbleiben,
nachdem man davon alle durch irgend eine der Primzahlen, A,,... 4
teilbaren Glieder abgezogen hat. Man erhält daher schliefslich:
p ) P ) - (, (C ')
eine Formel, welche zur Bestimmung der Gröfse P (-) mittelst zweier
andern ähnlichen Gröfsen dient, bei denen aber eine Primzahl weniger
in Betracht zu ziehen ist.
Da die Zahl C' im Allgemeinen verschieden ist von C, so ist
die Progression A - C', 2A - C',... ebenfalls von der gegebenen
Progression verschieden; sie besitzen jedoch beide dieselbe Differenz A.
Aus diesem Grunde haben wir die auf diese neue Progression bebezügliche Gröfse Pt -) durch einen dem Buchstaben P hinzugefügten
Strich von der andern unterschieden.
Ubrigens sieht man, dafs C' unmittelbar durch den Wert
C' A -+ C und ebenso n' durch die Formel n' = ( -E ge-o
funden wird.
428.
Die beiden Progressionen, von denen soeben die Rede war, reducieren sich auf eine einzige, wenn A = 2, C = 1, oder wenn es sich
um die Progression 1, 3, 5,... 2n - 1 handelt. Alsdann hat man:
~C0 - (_ - 1), C' n '-= E( + - -- )
und unsere Reduktionsformel geht über in:
l(') - - ^( -)- 3 )~ (d)
Diese Formel enthält eine Art von Algorithmus, der nützliche Anwendungen zuläfst.
Wir nehmen z. B. an, dafs man mit Hülfe der Tafel der Primzahlen blofs von 1 bis 100 wissen wolle, wieviel Primzahlen es von
1 bis 1000 giebt. Die Primzahl, welche unmittelbar unterhalb /1000