Wir benutzen
Fakt
und haben zu bestimmen, wie viele der Zahlen
,
,
in
liegen. Nun ist
genau dann, wenn
ist
(alle zu betrachtenden Vielfachen von
sind kleiner als
).
Dies ist äquivalent zu
und wir haben das kleinste
mit dieser Eigenschaft zu finden. Ist
ein Vielfaches von
, so ist
das kleinste
und insgesamt gibt es in diesem Fall
-
![{\displaystyle {}{\frac {p-1}{2}}-{\left({\frac {p-1}{4}}+1\right)}+1={\frac {p-1}{4}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c021447800640129cd0b8bd09ad2aec677c4f2ad)
solche
. Diese Anzahl ist bei
gerade und bei
ungerade, was das Ergebnis in diesen Fällen ergibt.
Es sei also nun
bzw.
. Dann ist das kleinste
derart, dass
ist, gleich
, und es gibt insgesamt
-
![{\displaystyle {}{\frac {p-1}{2}}-{\left({\frac {p-1}{4}}+{\frac {1}{2}}\right)}+1={\frac {p-1}{4}}+{\frac {1}{2}}={\frac {p+1}{4}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4913e92429115f4788fc458d704ab38b1f95e9bb)
solche
. Diese Anzahl ist bei
ungerade und bei
gerade, was die Behauptung in diesen Fällen ergibt.