einige Sätze über Anzahl und Anordnung quadratischer Reste modulo einer Primzahl p, also derjenigen primen Restklassen a modulo p, für die es ein x ∈ ℤ gibt, welches die Kongruenz \begin{eqnarray}{x}^{2}\equiv a\quad \mathrm{mod}\quad p\end{eqnarray} erfüllt (Legendre-Symbol).

Für kleine Primzahlen lassen sich die quadratischen Reste leicht durch direktes Rechnen ermitteln; so sind z. B. die Zahlen \begin{eqnarray}1,4,5,6,7,9,11,16,17\end{eqnarray} sämtliche quadratischen Reste modulo 19. (Die 0 zählt in der Regel nicht als quadratischer Rest, da nur die primen Restklassen betrachtet werden.)

Ein erstes Resultat ist folgendes:

Ist p ≠ 2 eine Primzahl, so gibt es unter den primen Restklassen modulo p genau \(\frac{1}{2}(p-1)\)quadratische Reste, und ebensoviele quadratische Nichtreste.

Ein zweites Resultat:

Ist p > 3 eine Primzahl mit \(p\equiv 3\) mod 4, so gibt eine natürliche Zahl \(n\lt 2\sqrt{p}+1\)die quadratischer Nichtrest modulo p ist.

Man interessiert sich nun insbesondere für die Anzahl der d-Tupel aufeinanderfolgender natürlicher Zahlen \begin{eqnarray}(t,t+1,\mathrm{\ldots},t+d-1)\end{eqnarray} mit 1 ≤ t und t + d ≤ p, die die Eigenschaft haben, daß jede Zahl aus diesem d-Tupel ein quadratischer Rest modulo p ist; diese Anzahl wird mit Qp(d) bezeichnet.

Nach dem ersten Resultat gilt \begin{eqnarray}Qp(d)=\left\{\begin{array}{ll}\frac{1}{2}(p-1) & \mathrm f\ddot{\mathrm u}\mathrm r\,d=1,\\ 0 & \mathrm f\ddot{\mathrm u}\mathrm r\,d\gt \frac{1}{2}(p-1).\end{array}\right.\end{eqnarray}Für d = 2 kann man aus der Liste (1) schon Q₁₉(2) = 4 ablesen.

Auf Gauß geht die allgemeine Berechnung von Q_p(2) zurück:

Ist p ≠ 2 eine Primzahl, dann gilt\begin{eqnarray}{Q}_{p}(2)=\frac{1}{4}(p-4+{(-1)}^{(p+1)/2)}).\end{eqnarray}

Für Aussagen über d = 3 benutzt man die Jacobsthalschen Summen.