Kurs:Zahlentheorie (Osnabrück 2016-2017)/Vorlesung 7

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Quadratische Reste modulo einer Primzahl

Modulo ist jede Zahl ein quadratischer Rest. Für ungerade Primzahlen kann man ebenfalls sofort eine Aussage über die Anzahl der Quadratreste machen.



Satz  

Sei eine ungerade Primzahl. Dann gibt es quadratische Reste modulo und nichtquadratische Reste modulo .

Beweis  

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“, so dass 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.


Bemerkung  

Wenn zu einer Primzahl eine primitive Einheit vorliegt, so hat man einen Gruppenisomorphismus

Dabei entsprechen die Quadrate rechts denjenigen Elementen links, die ein Vielfaches der sind. Bei ungerade besitzt die Hälfte der Elemente links diese Eigenschaft. Insbesondere ist ein Element genau dann ein Quadratrest, wenn es von der Form

ist.



Definition  

Für eine ungerade Primzahl und eine zu teilerfremde Zahl definiert man das Legendre-Symbol, geschrieben (sprich „ nach “), durch

Insbesondere ist . Die Werte des Legendre-Symbols, also und , kann man dabei in , in oder in auffassen. Für Vielfache von definierte man manchmal das Legendre-Symbol ebenfalls, und zwar mit dem Wert .



Lemma  

Sei eine ungerade Primzahl. Dann ist die Abbildung

ein Gruppenhomomorphismus.

Beweis  

Die Quadrate bilden offenbar eine Untergruppe in der Einheitengruppe , die nach Satz 7.1 den Index besitzt. Daher ist

und die Restklassenabbildung ist gerade die Abbildung auf das Legendre-Symbol.


Die folgende Aussage heißt das Euler-Kriterium für quadratische Reste.



Satz  

Sei eine ungerade Primzahl. Dann gilt für eine zu teilerfremde Zahl die Gleichheit

Beweis  

Es ist nach Lemma 4.6. Daher ist

Die Abbildung

ist (wie jedes Potenzieren) ein Gruppenhomomorphismus. Die Quadrate werden darunter auf abgebildet, da für die Gleichheit

gilt. Da nach Satz 5.11 die Einheitengruppe zyklisch ist, muss diese Abbildung surjektiv sein (sonst hätte jedes Element eine kleinere Ordnung). Damit muss diese Abbildung mit der durch das Legendre-Symbol gegebenen übereinstimmen.




Das Quadratische Reziprozitätsgesetz

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 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.



Satz

Seien und zwei verschiedene ungerade Primzahlen. Dann gilt:

Beweis

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


In Worten: Wenn und beide den Rest modulo haben, so ist modulo ein quadratischer Rest genau dann, wenn modulo ein nichtquadratischer Rest ist. In allen anderen Fällen ist modulo ein quadratischer Rest genau dann, wenn modulo ein quadratischer Rest ist.


Beispiel  

Betrachten wir die beiden Primzahlen und , die beide modulo den Rest haben. Es ist modulo und dies ist nach Beispiel 6.4 kein Quadratrest. Gemäß dem Reziprozitätsgesetz muss also modulo ein quadratischer Rest sein. In der Tat ist

Betrachtet man hingegen die Primzahlen und , so hat modulo den Rest und hat modulo den Rest . Es ist ein nichtquadratischer Rest, und daher ist auch ein nichtquadratischer Rest modulo .


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



Satz  

Für eine ungerade Primzahl gilt:

Beweis  

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



Satz

Für eine ungerade Primzahl gilt:

Beweis

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


Beispiel  

In ist und . Für 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

die Vorzeichen sind also der Reihe nach

Ihr Produkt ist , und mit dem folgenden Gaußschen Vorzeichenlemma folgt, dass ein Quadratrest ist. In der Tat ist .


Die folgende Aussage heißt Gaußsches Vorzeichenlemma.



Lemma  

Für eine ungerade Primzahl und eine zu teilerfremde Zahl gilt mit den zuvor eingeführten Bezeichnungen

Beweis  

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.



Satz  

Für eine ungerade Primzahl gilt:

Beweis  

Wir benutzen Lemma 7.11 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.

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.



<< | Kurs:Zahlentheorie (Osnabrück 2016-2017) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)