Für ungerade Primzahlen kann man sofort eine Aussage über die Anzahl der Quadratreste machen.
Zunächst ist ein quadratischer Rest. Wir betrachten im folgenden nur noch die Einheiten in
(also die von verschiedenen Reste)
und zeigen, dass es darunter gleich viele quadratische und nichtquadratische Reste gibt. Die Abbildung
-
ist offenbar ein Gruppenhomomorphismus der Einheitengruppe in sich selbst. Ein Element ist genau dann ein Quadratrest, wenn es im Bild dieses Homomorphismus liegt. Nach dem Isomorphiesatz ist „Bild = Urbild modulo Kern“, sodass wir den Kern bestimmen müssen. Der Kern besteht aus allen Elementen mit
Dazu gehören
und ,
und diese beiden Elemente sind verschieden, da ungerade ist. Aus der polynomialen Identität
folgt, dass es keine weiteren Lösungen geben kann. Der Kern besteht also aus genau Elementen und damit besteht das Bild aus Elementen.
Insbesondere ist . Die Werte des Legendre-Symbols, also und , kann man dabei in , in oder in auffassen.
Es sei eine ungerade Primzahl. Dann ist die Abbildung
-
ein
Gruppenhomomorphismus.
Seien und zwei ungerade Primzahlen. Dann kann ein quadratischer Rest modulo sein (oder nicht) und kann ein quadratischer Rest modulo sein, oder nicht. Das Quadratische Reziprozitätsgesetz, das von Euler entdeckt und von Gauss 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 quadratischer Nichtrest ist.
Es seien
und
verschiedene ungerade
Primzahlen. Dann gilt:
-
Dies wird weiter unten nach einigen Vorbereitungen bewiesen. Die zweite Gleichung ist elementar.
Die beiden folgenden Sätze werden die Ergänzungssätze zum quadratischen Reziprozitätsgesetz genannt.
Für eine ungerade Primzahl gilt:
-
Die Gleichung von links und rechts wurde bereits in
Satz 6.7
bewiesen. Die erste Gleichung ist auch ein Spezialfall von
Satz 7.4
und die zweite Gleichung ist elementar.
Für eine ungerade Primzahl gilt:
-
Dies wird weiter unten bewiesen.
Die Elemente im Restklassenkörper werden meist durch die Zahlen von bis repräsentiert. Für das folgende Vorzeichenlemma von Gauß ist es sinnvoll, ein anderes Repräsentantensystem
(für die von verschiedenen Elemente)
zu fixieren. Wir setzen und
-
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 teilerfremden Zahl die Menge der Vielfachen
, ,
in und schaut, ob sie in der negativen oder der positiven Hälfte liegen. Man definiert die sogenannten Gaußschen Vorzeichen
-
Es sei durch die Bedingung
-
festgelegt. Wir betrachten alle Vielfachen , . Die Menge all dieser Vielfachen ist selbst ganz , da ja eine Einheit und daher die Multiplikation mit eine Bijektion ist. Es ist für . Daher ist . Deshalb gilt und somit
-
Durch kürzen mit
(das ist eine Einheit)
ergibt sich
-
und
das Euler-Kriterium,
nämlich
-
liefert das Ergebnis.
Mit dem Gaußschen Vorzeichenlemma beweisen wir zunächst den zweiten Ergänzungssatz zum quadratischen Reziprozitätsgesetz, der beschreibt, wann ein quadratischer Rest ist.
Für eine ungerade Primzahl gilt:
-
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
-
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
-
solche . Diese Anzahl ist bei ungerade und bei gerade, was die Behauptung in diesen Fällen ergibt.