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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Beweis des quadratischen Reziprozitätsgesetzes

Im nächsten Lemma verwenden wir folgende Notation:

Zu einer ungeraden Primzahl und einer Zahl sei



Lemma  Lemma 8.1 ändern

Sei eine ungerade Primzahl und kein Vielfaches von . Dann gelten folgende Aussagen.

  1. Es ist , wobei wie im Gaußsches Vorzeichenlemma definiert ist.
  2. Es ist .
  3. Ist ungerade, so ist .

Beweis  

  1. Zur Berechnung von muss man bestimmen, ob der betragsmäßig kleinste Repräsentant von in positiv oder negativ ist. Dies hängt davon ab, ob zu einem Intervall der Form oder der Form gehört (wobei die Ränder wegen den Voraussetzungen unproblematisch sind). Dies hängt davon ab, ob gerade oder ungerade ist.
  2. Aus Teil (1) und dem Gaußschen Vorzeichenlemma folgt wegen (mit )

    die Behauptung.

  3. Sei nun ungerade. Dann ist eine ganze Zahl. Unter Verwendung von Teil (2) erhält man

    Für den Exponenten rechts gilt

    Wegen folgt nach dem zweiten Ergänzungssatz die Identität

    Man kann daher in der Gesamtgleichungskette

    kürzen und erhält die Aussage.


Wir können nun das quadratische Reziprozitätsgesetz beweisen.



Satz  Referenznummer erstellen

Seien und zwei verschiedene ungerade Primzahlen. Dann gilt:

Beweis  

Sei und . Nach Lemma 8.1  (3) gilt , so dass also zu zeigen ist. Betrachte

Diese Menge besitzt Elemente, und , da ja und teilerfremd sind. Es seien die negativen Elemente aus und die positiven Elemente aus . Es ist genau dann, wenn ist, was genau für der Fall ist. Zu jedem , , gibt es also genau Elemente in . Damit hat genau

Elemente. Die entsprechende Überlegung liefert, dass genau Elemente besitzt, woraus

folgt.


Das quadratische Reziprozitätsgesetz kann man auch so formulieren: Sind und zwei verschiedene ungerade Primzahlen, so gilt:

Damit kann man die Berechnung von auf die Berechnung von zurückführen. Darauf beruht der folgende Algorithmus.

Bemerkung   Referenznummer erstellen

Seien und ungerade verschiedene Primzahlen, und man möchte berechnen, also herausfinden, ob ein quadratischer Rest modulo ist oder nicht. Ist , so berechnet man zuerst den Rest , und ersetzt durch den kleineren Rest, der natürlich keine Primzahl sein muss. Ist hingegen , so berechnet man die Reste von und modulo und kann dann mittels dem quadratischen Reziprozitätsgesetz auf zurückführen. In beiden Fällen kommt man also auf eine Situation, wo zu berechnen ist, wo eine ungerade Primzahl ist und beliebig.

Sei die Primfaktorzerlegung von . Dann ist nach der Multiplikativität des Legendre-Symbols

Jetzt kann nach dem zweiten Ergänzungsgesetz berechnet und die können für nach dem gleichen Verfahren auf die Berechnung von zurückgeführt werden (von den Exponenten kommt es nur auf die Parität an). Bei diesem Verfahren werden natürlich die Nenner (und damit auch die Zähler) in den Legendre-Symbolen kleiner, so dass man schließlich das Resultat erhält.



Beispiel  Referenznummer erstellen

Man möchte entscheiden, ob die Gleichung

eine Lösung besitzt. Dazu berechnet man

Der erste Faktor

lässt sich mit Hilfe des zweiten Ergänzungssatzes zu bestimmen, weil und ergibt das Vorzeichen .

Um den zweiten Faktor zu berechnen, wendet man das Reziprozitätsgesetz an:

weil gilt (der Rest braucht gar nicht mehr berechnet zu werden, da es ausreicht, dass hier oder modulo den Rest lässt, damit das Vorzeichen ist). Jetzt nutzt man aus, dass ist. Man schreibt:

Wiederum wendet man hier das Quadratische Reziprozitätsgesetz an: Es ist

da ist und da kein Quadrat modulo ist.

Setzt man nun beide Faktoren zusammen, so ergibt sich folgendes Resultat:

Damit weiß man, dass die obige Gleichung eine Lösung besitzt (die beiden Lösungen lauten und .). Auf dieses Ergebnis kommt man leider nur durch Probieren. Hat man aber eine Lösung, z.B. die , so berechnet man die zweite Lösung, indem man das additive Inverse im Körper bestimmt ()



Beispiel  Referenznummer erstellen

Man möchte entscheiden, ob die Gleichung

eine Lösung besitzt. Dazu berechnet man

und kann wie oben die beiden Faktoren mit dem Reziprozitätsgesetz weiter vereinfachen:

und

Setzt man alles zusammen, so ergibt sich

und damit die Erkenntnis, dass die obige Gleichung keine Lösung besitzt.




Das Jacobi-Symbol

Zur Berechnung des Legendre-Symbols muss man die Primfaktorzerlegung der beteiligten Zahlen kennen, was für große Zahlen ein erheblicher Rechenaufwand darstellen kann. Die Einführung des Jacobi-Symbols erlaubt es, zu entscheiden, ob eine Zahl quadratischer Rest ist oder nicht, ohne Primfaktorzerlegungen zu kennen.


Definition  Referenznummer erstellen

Für eine ungerade Zahl und eine ganze Zahl definiert man das Jacobi-Symbol, geschrieben ( nach ), wie folgt. Es sei die Primfaktorzerlegung von . Dann setzt man


Im Fall eine ungerade Primzahl ist das Jacobi-Symbol nichts anderes als das Legendre-Symbol. Das Jacobi-Symbol ist also eine Verallgemeinerung des Legendre-Symbols. Es ist aber zu beachten, dass die inhaltliche Definition des Legendre-Symbols sich im allgemeinen nicht auf das Jacobi-Symbol überträgt. Das Jacobi-Symbol ist nicht genau dann , wenn ein Quadrat modulo ist. Die Definition des Jacobi-Symbols nimmt Bezug auf die Primfaktorzerlegung von , was wir eigentlich vermeiden wollten. Der Punkt ist aber, dass man das Jacobi-Symbol berechnen kann, auch wenn man die Primfaktorzerlegung gar nicht kennt.



Lemma  Lemma 8.7 ändern

Seien ganze Zahlen und seien ungerade positive Zahlen. Dann gelten folgende Aussagen.

  1. Das Jacobi-Symbol hängt nur vom Rest ab.
  2. Es ist .
  3. Es ist .

Beweis  

Diese Aussagen folgen sofort aus der Definition des Jacobi-Symbols bzw. aus der Multiplikativität des Legendre-Symbols im Zähler.


Für das Jacobi-Symbol gilt das quadratische Reziprozitäts mitsamt den Ergänzungssätzen.


Satz

Seien und positive ungerade Zahlen. Dann gelten folgende Aussagen.

  1. .
  2. .
  3. .

Beweis

Diese Aussagen werden in den Aufgaben bewiesen.


Bemerkung   Referenznummer erstellen

Seien und ungerade verschiedene Zahlen, und man möchte das Jacobi-Symbol berechnen (man berechnet im Allgemeinen nicht, ob ein quadratischer Rest modulo ist, dies ist nur dann der Fall, wenn eine Primzahl ist). Durch die Restberechnung können wir sofort annehmen, dass ist. Wir schreiben

wobei ungerade sei. Dann gilt nach Lemma 8.7

Hier kann, nach dem quadratischen Reziprozitätsgesetz für das Jacobi-Symbol (und der Ergänzungssätze), berechnet werden und kann auf zurückgeführt werden. Bei diesem Verfahren werden natürlich die Nenner (und damit auch die Zähler) in den Jacobi-Symbolen kleiner, so dass man schließlich das Resultat erhält.


Wenn eine Primzahl ist, so kann man mit diesem Algorithmus, also unter Verwendung des Jacobi-Symbols, entscheiden, ob ein Quadratrest modulo ist. In den Zwischenschritten braucht man nicht die Primfaktorzerlegungen auszurechnen.

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

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)