Die Elemente der Zahlentheorie / dargestellt von Paul Bachmann.

118 Dritter Abschnitt
entscheiden, von welchen ungeraden Primzahlen p eine
gegebene Zahl n quadratischer Rest resp. Nichtrest
ist. Dies hängt aber nach dem aus dem Euler'schen Criterium gewonnenen Satze in No. 2 wieder davon ab, wie sich
bezüglich des Modulus p die Faktoren verhalten, in welche n
zerlegbar ist; und da n positiv oder negativ, gerade oder ungerade sein kann, so wird unsere Untersuchung schliesslich
auf eine der drei folgenden Fragen zurückkommen:
1) Von welchen ungeraden Primzahlen p ist -- 1
quadratischer Rest oder Nichtrest?
2) Von welchen ist es die Zahl 2?
3) Von welchen ist es eine andere ungerade Primzahl q?
Die erste dieser Fragen beantwortet sich augenblicklich
mit Hilfe des Euler'schen Criteriums, nach welchem allgemein
29 —1
(p) ~ 2~ (mod.p)
ist. Denn für n =- 1 giebt es diese Congruenz:
P-1
(-) -(- 1) 2 (mod. p);
rechts und links stehen aber Ausdrücke, welche nur -+ 1 oder
- 1 bedeuten können; wären sie einander nicht gleich, so
müssten -- 1 und - 1 (mod. p) congruent, d. h. 2 durch p
theilbar sein, was nicht der Fall ist, und folglich schliesst
man die Gleichung:
P-1
(18) (_ )
In Worten besagt dieselbe folgenden eleganten, auch
schon von Fermat*) gegebenen Satz:
Die Zahl - 1 ist quadratischer Rest von jeder
Primzahl p von der Form 4k + 1, quadratischer Nichtrest von jeder Primzahl p von der Form 4k + 3; der
*) Euler hat zuerst diesen Satz bewiesen; s. z. B. seine Abhandl.
observationes circa divisionem quadratorum per numeros primos, in
Opusc. analyt. I p. 64, oder commentationes arithmeticae collectae I,
p. 477, das. im theorema IV und V.