ein Satz über das Rechnen mit dem Legendre-Symbol:

Seien p ≠ q ungerade Primzahlen. Dann gilt \begin{eqnarray}\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)={(-1)}^{\frac{p-1}{2}.\frac{q-1}{2}}.\end{eqnarray}

Hinter dem quadratischen Reziprozitätsgesetz steht die Frage, unter welchen Bedingungen an zwei gegebene Zahlen a ∈ ℤ und m ∈ ℕ die quadratische Kongruenz \begin{eqnarray}\begin{array}{cc}{X}^{2}\equiv a\,\,\text{mod}\,m\end{array}\end{eqnarray}

lösbar ist. Man nennt a einen quadratischen Rest modulo m, wenn es eine ganze Zahl X gibt, die (1) erfüllt, andernfalls einen quadratischen Nichtrest modulo m. Ist p eine ungerade Primzahl (d. h. p ≠ 2), und ist a nicht durch p teilbar, so ist das Legendre-Symbol gegeben durch \begin{eqnarray}\left(\frac{a}{p}\right)=\left\{\begin{array}{l}+1\,\,\text{falls}\,a\,\text{quadratischer Rest mod}\,m\text{,}\\ -1\,\,\text{sonst}\text{.}\end{array}\right.\end{eqnarray}

Um zu entscheiden, ob die Kongruenz (1) lösbar ist oder nicht, benutzt man zunächst den folgenden Satz:

Seien m ∈ ℕ und a ∈ ℤ teilerfremd, und sei \begin{eqnarray}m={2}^{{v}_{0}}{p}_{1}^{{v}_{1}}\cdots {p}_{k}^{vk}\end{eqnarray}

die kanonische Primfaktorzerlegung von m.

a ist genau dann ein quadratischer Rest modulo m, wenn \begin{eqnarray}\left(\frac{a}{{p}_{j}}\right)=1\end{eqnarray}

für alle j = 1,…,k ist, und außerdem gilt: \begin{eqnarray}\begin{array}{ccc}a\equiv 1 & \mathrm{mod} & {2}^{\min \{{v}_{0},3\}}\end{array}.\end{eqnarray}

Ist weiterhin \begin{eqnarray}|a|={2}^{{\beta }_{0}}{q}_{1}^{{\beta }_{1}}\cdots {q}_{\ell }^{\beta \ell }\end{eqnarray}

die kanonische Primfaktorzerlegung von |a|, und ist p eine ungerade Primzahl, die kein Teiler von a ist, so gilt \begin{eqnarray}\left(\frac{a}{p}\right)=\left\{\begin{array}{ll}{\left(\displaystyle\frac{{q}_{1}}{p}\right)}^{{\beta }_{1}}\cdots {\left(\displaystyle\frac{q\ell }{p}\right)}^{\beta \ell } & {f}\ddot{ u}{r}\quad \text{}a\gt 0,\\ \left(\displaystyle\frac{-1}{p}\right){\left(\displaystyle\frac{q1}{p}\right)}^{{\beta }_{1}}\cdots {\left(\displaystyle\frac{q\ell }{p}\right)}^{{\beta }_{\ell }} & {f}\ddot{u}{ r}\quad \text{}a\lt 0.\end{array}\right.\end{eqnarray}

Damit ist die Frage nach notwendigen und hinreichenden Bedingungen zur Lösbarkeit von (1) auf die Bestimmung der Legendre-Symbole \begin{eqnarray}\begin{array}{ccc}\left(\displaystyle\frac{-1}{p}\right), & \left(\displaystyle\frac{2}{p}\right), & \left(\displaystyle\frac{q}{p}\right)\end{array}\end{eqnarray}

zurückgeführt, wobei p, q voneinander verschiedene ungerade Primzahlen sind. Das quadratische Reziprozitätsgesetz, zusammen mit seinen beiden Ergänzungssätzen, liefert einen einfachen Algorithmus zur Berechnung der Legendre-Symbole. Der erste Ergänzungssatz lautet:

Für jede Primzahl p ≠ 2 gilt \begin{eqnarray}\left(\frac{-1}{p}\right)={(-1)}^{(p-1)/2}.\end{eqnarray}

Der zweite Ergänzungssatz:

Für jede Primzahl p ≠ 2 gilt \begin{eqnarray}\left(\frac{2}{p}\right)={(-1)}^{({p}^{2}-1)/8}.\end{eqnarray}

In seinen „Disquisitiones Arithmeticae“ beschreibt Gauß anhand eines Beispiels diesen Algorithmus zur Beantwortung der Frage, ob eine Kongruenz (1) lösbar ist. Er behandelt die Kongruenz \begin{eqnarray}{X}^{2}\equiv 453\quad\text{mod}\quad1236\end{eqnarray}

und stellt nicht nur fest, daß diese lösbar ist, sondern gibt auch gleich die Lösung:…est autem revera 453 ≡ 297² (mod 1236).

Die beiden Ergänzungssätze zum quadratischen Reziprozitätsgesetz waren bereits Fermat bekannt; Euler gab einen Beweis des ersten, und Lagrange bewies den zweiten Ergänzungssatz. Das quadratische Reziprozitätsgesetz selbst wurde von Euler (ohne Beweis) benutzt. Legendre nannte es „loi de réciprocité“ und gab einen lückenhaften Beweis. Gauß fand 1796 das Reziprozitätsgesetz zunächst mit Hilfe umfangreichen Beispielmaterials und lieferte schließlich insgesamt acht methodisch verschiedene Beweise. Bis heute sind mehr als 150 weitere Beweise publiziert worden.

Gauß begann auch damit, analoge Reziprozitätsgesetze für Kongruenzen höheren als zweiten Grades aufzustellen. Die Frage nach dem „allgemeinsten Reziprozitätsgesetz im beliebigen Zahlkörper“ wurde 1900 von Hilbert als neuntes in seine Liste von 23 mathematischen Problemen aufgenommen (Hilbertsche Probleme). Es wurde 1950 schließlich gelöst, vor allem durch Arbeiten von Tagaki, Hasse, Artin und Safarevic.