Quadratisches Reziprozitätsgesetz/Hinführung und Vorbereitung/Textabschnitt

Es seien ${}p$ und ${}q$ zwei ungerade Primzahlen. Dann kann ${}p$ ein quadratischer Rest modulo ${}q$ sein (oder nicht) und ${}q$ kann ein quadratischer Rest modulo ${}p$ sein, oder nicht. Das Quadratische Reziprozitätsgesetz, das von Euler entdeckt und von Gauß erstmals bewiesen wurde, behauptet nun, dass es einen direkten Zusammenhang zwischen diesen beiden Eigenschaften gibt. Es erlaubt weiterhin mit den beiden unten genannten Ergänzungssätzen algorithmisch zu entscheiden, ob eine Zahl ein quadratischer Rest oder ein nichtquadratischer Rest ist.

Carl Friedrich Gauss (1777-1855)

Satz

Es seien ${}p$ und ${}q$ verschiedene ungerade Primzahlen. Dann gilt:

${}\left({\frac {p}{q}}\right)\cdot \left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}={\begin{cases}-1\,,{\text{ wenn }}p=q=3\mod 4\,,\\1\,,{\text{ sonst}}\,.\end{cases}}\,$

Beweis

Dies wird weiter unten nach einigen Vorbereitungen bewiesen. Die zweite Gleichung ist elementar.

$\Box$

In Worten: Wenn ${}p$ und ${}q$ beide den Rest ${}3$ modulo ${}4$ haben, so ist ${}p$ modulo ${}q$ ein quadratischer Rest genau dann, wenn ${}q$ modulo ${}p$ ein nichtquadratischer Rest ist. In allen anderen Fällen ist ${}p$ modulo ${}q$ ein quadratischer Rest genau dann, wenn ${}q$ modulo ${}p$ ein quadratischer Rest ist.

Beispiel

Betrachten wir die beiden Primzahlen ${}11$ und ${}19$, die beide modulo ${}4$ den Rest ${}3$ haben. Es ist  ${}19=8$  modulo ${}11$ und dies ist nach Beispiel kein Quadratrest. Gemäß dem Reziprozitätsgesetz muss also ${}11$ modulo ${}19$ ein quadratischer Rest sein. In der Tat ist

${}7^{2}=49=11\mod 19\,.$

Betrachtet man hingegen die Primzahlen ${}11$ und ${}13$, so hat ${}11$ modulo ${}4$ den Rest ${}3$ und ${}13$ hat modulo ${}4$ den Rest ${}1$. Es ist  ${}13=2\mod 11$  ein nichtquadratischer Rest, und daher ist auch ${}11$ ein nichtquadratischer Rest modulo ${}13$.

Die beiden folgenden Sätze werden die Ergänzungssätze zum quadratischen Reziprozitätsgesetz genannt, da sie klären, wann die ${}-1$ und wann die ${}2$ quadratische Reste sind. In der algorithmischen Bestimmung von Quadratresten sind diese beiden Fälle ebenfalls unerlässlich.

Satz

Für eine ungerade Primzahl ${}p$ gilt:

${}\left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}1\,,{\text{ falls }}p=1\mod 4\,,\\-1\,,{\text{ sonst }}{\text{(also bei }}p=3\mod 4{\mbox{)}}\,.\end{cases}}\,$

Beweis

Die Gleichung von links und rechts wurde bereits in Fakt bewiesen. Die erste Gleichung ist auch ein Spezialfall von Fakt und die zweite Gleichung ist elementar.

$\Box$

Satz

Für eine ungerade Primzahl ${}p$ gilt:

${}\left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}=\left\{{\begin{matrix}1\,,&{\mbox{falls}}&p=\pm 1\mod 8\,,\\-1&{\mbox{sonst}}&{\mbox{(also }}p=\pm 3\mod 8{\mbox{)}}&\,.\end{matrix}}\right.\,$

Beweis

Dies wird weiter unten bewiesen.

$\Box$

Die Elemente im Restklassenkörper ${}\mathbb {Z} /(p)$ werden zumeist durch die Zahlen von ${}0$ bis ${}p-1$ repräsentiert. Für das Vorzeichenlemma von Gauß ist es sinnvoll, ein anderes Repräsentantensystem (für die von ${}0$ verschiedenen Elemente) zu fixieren. Wir setzen  ${}t={\frac {p-1}{2}}$  und

$S=S_{-}\cup S_{+}{\text{ mit }}S_{-}=\{-t,-t+1,\ldots ,-2,-1\}{\text{ und }}S_{+}=\{1,2,\ldots ,t-1,t\}.$

Wir unterteilen also die Einheitengruppe in eine positive und eine negative Hälfte. Dieses Repräsentantensystem ist dadurch ausgezeichnet, dass jedes Element durch das betragmäßig kleinste Element repräsentiert wird. Im folgenden Lemma betrachtet man zu einer zu ${}p$ teilerfremden Zahl ${}k$ die Menge der Vielfachen ${}ik$, ${}i=1,\ldots ,t$, in ${}\mathbb {Z} /(p)$ und schaut, ob sie in der negativen oder der positiven Hälfte liegen. Man definiert die sogenannten Gaußschen Vorzeichen

${}\epsilon _{i}=\epsilon _{i}(k)={\begin{cases}1,{\text{ falls }}ik\in S_{+}\,,\\-1,{\text{ falls }}ik\in S_{-}\,.\end{cases}}\,$

Beispiel

In ${}\mathbb {Z} /(11)$ ist  ${}S_{+}=\{1,2,3,4,5\}$  und  ${}S_{-}=\{-1,-2,-3,-4,-5\}$.  Für  ${}k=3$  muss man, um die Gaußschen Vorzeichen zu bestimmen, die ersten fünf Vielfachen berechnen und schauen, ob sie zur negativen oder zur positiven Hälfte gehören. Es ist

$3\in S_{+},\,6=-5\in S_{-},\,9=-2\in S_{-},\,12=1\in S_{+},\,15=4\in S_{+},$

die Vorzeichen sind also der Reihe nach

$1,-1,-1,1,1.$

Ihr Produkt ist ${}1$, und mit dem folgenden Gaußschen Vorzeichenlemma folgt, dass ${}3$ ein Quadratrest modulo ${}11$ ist. In der Tat ist  ${}3=5^{2}\mod 11$. 

Die folgende Aussage heißt Gaußsches Vorzeichenlemma.

Lemma

Für eine ungerade Primzahl ${}p$ und eine zu ${}p$ teilerfremde Zahl ${}k$ gilt mit den zuvor eingeführten Bezeichnungen

${}\left({\frac {k}{p}}\right)=\epsilon _{1}\cdot \epsilon _{2}\cdots \epsilon _{t}\,.$

Beweis

Es sei  ${}s_{i}\in S_{+}$  durch die Bedingung

${}ik=\epsilon _{i}s_{i}\mod p\,$

festgelegt. Wir betrachten alle Vielfachen ${}jk$,  ${}j\in S={\left(\mathbb {Z} /(p)\right)}^{\times }$.  Die Menge all dieser Vielfachen ist selbst ganz ${}S$, da ja ${}k$ eine Einheit und daher die Multiplikation mit ${}k$ eine Bijektion ist. Es ist  ${}(-i)k=-ik=-\epsilon _{i}s_{i}$  für  ${}i\in S_{+}=\{1,\ldots ,t\}$.  Daher ist  ${}S_{+}=\{1,\ldots ,t\}=\{s_{1},\ldots ,s_{t}\}$.  Deshalb gilt  ${}t!=\prod _{i=1}^{t}s_{i}$  und somit

${}t!k^{t}={\left(\prod _{i=1}^{t}i\right)}{\left(\prod _{i=1}^{t}k\right)}=\prod _{i=1}^{t}ik=\prod _{i=1}^{t}\epsilon _{i}s_{i}={\left(\prod _{i=1}^{t}\epsilon _{i}\right)}{\left(\prod _{i=1}^{t}s_{i}\right)}={\left(\prod _{i=1}^{t}\epsilon _{i}\right)}t!\mod p\,.$

Durch kürzen mit ${}t!$ (das ist eine Einheit) ergibt sich

${}k^{t}=\prod _{i=1}^{t}\epsilon _{i}\mod p\,,$

und das Euler-Kriterium, nämlich

${}k^{t}=k^{\frac {p-1}{2}}=\left({\frac {k}{p}}\right)\mod p\,,$

liefert das Ergebnis.

$\Box$

Mit dem Gaußschen Vorzeichenlemma beweisen wir zunächst den zweiten Ergänzungssatz zum quadratischen Reziprozitätsgesetz, der beschreibt, wann ${}2$ ein quadratischer Rest ist.

Satz

Für eine ungerade Primzahl ${}p$ gilt:

${}\left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}=\left\{{\begin{matrix}1\,,&{\mbox{falls}}&p=\pm 1\mod 8\,,\\-1&{\mbox{sonst}}&{\mbox{(also }}p=\pm 3\mod 8{\mbox{)}}&\,.\end{matrix}}\right.\,$

Beweis

Wir benutzen Fakt und müssen bestimmen, wie viele der Zahlen ${}2i$, ${}i=1,\ldots ,t={\frac {p-1}{2}}$, in ${}S_{-}$ liegen. Nun ist  ${}2i\in S_{-}$  genau dann, wenn  ${}2i>{\frac {p-1}{2}}$  ist (alle zu betrachtenden Vielfachen von ${}2$ sind kleiner als ${}p$). Dies ist äquivalent zu  ${}i>{\frac {p-1}{4}}$  und wir müssen das kleinste ${}i$ mit dieser Eigenschaft finden. Ist ${}p-1$ ein Vielfaches von ${}4$, so ist ${}{\frac {p-1}{4}}+1$ das kleinste ${}i$ und insgesamt gibt es in diesem Fall

${}{\frac {p-1}{2}}-{\left({\frac {p-1}{4}}+1\right)}+1={\frac {p-1}{4}}\,$

solche ${}i$. Diese Anzahl ist bei  ${}p=1\mod 8$  gerade und bei  ${}p=5\mod 8$  ungerade, was das Ergebnis in diesen Fällen ergibt.

Es sei also nun  ${}p=3,7\mod 8$  bzw.  ${}p=3\mod 4$.  Dann ist das kleinste ${}i$ derart, dass  ${}i>{\frac {p-1}{4}}$  ist, gleich ${}{\frac {p-1}{4}}+{\frac {1}{2}}$, und es gibt insgesamt

${}{\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}}\,$

solche ${}i$. Diese Anzahl ist bei  ${}p=3\mod 8$  ungerade und bei  ${}p=7\mod 8$  gerade, was die Behauptung in diesen Fällen ergibt.

$\Box$