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

Beweis des quadratischen Reziprozitätsgesetzes

Im nächsten Lemma verwenden wir folgende Notation:

Zu einer ungeraden Primzahl ${}p$ und einer Zahl ${}k\in \mathbb {Z}$ sei

${}S(k,p)=\sum _{i=1}^{\frac {p-1}{2}}\left\lfloor {\frac {ki}{p}}\right\rfloor \,.$

Lemma Lemma 8.1 ändern

Es sei ${}p$ eine ungerade Primzahl und ${}k\in \mathbb {Z}$ kein Vielfaches von ${}p$. Dann gelten folgende Aussagen.

1. Es ist ${}\epsilon _{i}=(-1)^{\left\lfloor {\frac {2ki}{p}}\right\rfloor }$, wobei ${}\epsilon _{i}$ wie im Gaußsches Vorzeichenlemma definiert ist.
2. Es ist ${}\left({\frac {k}{p}}\right)=(-1)^{S(2k,p)}$.
3. Ist ${}k$ ungerade, so ist ${}\left({\frac {k}{p}}\right)=(-1)^{S(k,p)}$.

Beweis

1. Zur Berechnung von ${}\epsilon _{i}=\epsilon _{i}(k)$ muss man bestimmen, ob der betragsmäßig kleinste Repräsentant von ${}a=ki$ in ${}\mathbb {Z} /(p)$ positiv oder negativ ist. Dies hängt davon ab, ob ${}a$ zu einem Intervall der Form ${}[\ell p,\ell p+{\frac {p}{2}}]$ oder der Form ${}[\ell p+{\frac {p}{2}},(\ell +1)p]$ gehört (wobei die Ränder wegen den Voraussetzungen unproblematisch sind). Dies hängt davon ab, ob ${}\left\lfloor {\frac {2a}{p}}\right\rfloor$ gerade oder ungerade ist.
2. Aus Teil (1) und dem Gaußschen Vorzeichenlemma folgt wegen (mit ${}t={\frac {p-1}{2}}$)

   ${}\left({\frac {k}{p}}\right)=\prod _{i=1}^{t}\epsilon _{i}=\prod _{i=1}^{t}(-1)^{\left\lfloor {\frac {2ki}{p}}\right\rfloor }=(-1)^{S(2k,p)}\,$

   die Behauptung.

3. Es sei nun ${}k$ ungerade. Dann ist ${}(p+k)/2$ eine ganze Zahl. Unter Verwendung von Teil (2) erhält man

   ${}\left({\frac {2}{p}}\right)\left({\frac {k}{p}}\right)=\left({\frac {2k}{p}}\right)=\left({\frac {2(p+k)}{p}}\right)=\left({\frac {(p+k)/2}{p}}\right)=(-1)^{S(p+k,p)}\,.$

   Für den Exponenten rechts gilt

   ${}S(p+k,p)=\sum _{i=1}^{t}\left\lfloor {\frac {i(p+k)}{p}}\right\rfloor =\sum _{i=1}^{t}\left\lfloor {\frac {ik}{p}}\right\rfloor +\sum _{i=1}^{t}i=S(k,p)+{\frac {(t+1)t}{2}}\,.$

   Wegen ${}{\frac {(t+1)t}{2}}={\frac {(p+1)}{2}}\cdot {\frac {(p-1)}{2}}\cdot {\frac {1}{2}}={\frac {p^{2}-1}{8}}$ folgt nach dem zweiten Ergänzungssatz die Identität

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

   Man kann daher in der Gesamtgleichungskette

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

   kürzen und erhält die Aussage.

$\Box$

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

Satz Referenznummer erstellen

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

Es sei ${}t={\frac {p-1}{2}}$ und ${}u={\frac {q-1}{2}}$. Nach Lemma 8.1  (3) gilt ${}\left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{S(p,q)+S(q,p)}$, sodass also ${}tu=S(p,q)+S(q,p)$ zu zeigen ist. Betrachte

${}M={\left\{qi-pj\mid 1\leq i\leq t,\,1\leq j\leq u\right\}}\,.$

Diese Menge besitzt ${}tu$ Elemente, und ${}0\notin M$, da ja ${}p$ und ${}q$ teilerfremd sind. Es seien ${}M_{-}$ die negativen Elemente aus ${}M$ und ${}M_{+}$ die positiven Elemente aus ${}M$. Es ist ${}qi-pj>0$ genau dann, wenn

${}{\frac {qi}{p}}>j\,$

ist, was genau für ${}1\leq j=\left\lfloor {\frac {qi}{p}}\right\rfloor$ der Fall ist. Zu jedem ${}i$, ${}1\leq i\leq t$, gibt es also genau ${}\left\lfloor {\frac {qi}{p}}\right\rfloor$ Elemente in ${}M_{+}$. Damit hat ${}M_{+}$ genau

${}\sum _{i=1}^{t}\left\lfloor {\frac {qi}{p}}\right\rfloor =S(q,p)\,$

Elemente. Die entsprechende Überlegung liefert, dass ${}M_{-}$ genau ${}S(p,q)$ Elemente besitzt, woraus

${}tu={\#\left(M\right)}={\#\left(M_{+}\right)}+{\#\left(M_{-}\right)}=S(q,p)+S(p,q)\,$

folgt.

$\Box$

Das quadratische Reziprozitätsgesetz kann man auch so formulieren: Sind ${}p$ und ${}q$ zwei verschiedene ungerade Primzahlen, so gilt:

${}\left({\frac {p}{q}}\right)={\begin{cases}-\left({\frac {q}{p}}\right)\,,{\text{wenn}}p\equiv q\equiv 3{\pmod {4}}\,,\\\left({\frac {q}{p}}\right){\text{ sonst}}\,.\end{cases}}\,$

Damit kann man die Berechnung von ${}\left({\frac {p}{q}}\right)$ auf die Berechnung von ${}\left({\frac {q}{p}}\right)$ zurückführen. Darauf beruht der folgende Algorithmus.

Bemerkung   Referenznummer erstellen

Es seien ${}p$ und ${}q$ ungerade verschiedene Primzahlen, und man möchte ${}\left({\frac {p}{q}}\right)$ berechnen, also herausfinden, ob ${}p$ ein quadratischer Rest modulo ${}q$ ist oder nicht. Ist ${}p>q$, so berechnet man zuerst den Rest ${}p\mod q$, und ersetzt ${}p$ durch den kleineren Rest, der natürlich keine Primzahl sein muss. Ist hingegen ${}p<q$, so berechnet man die Reste von ${}p$ und ${}q$ modulo ${}4$ und kann dann mittels dem quadratischen Reziprozitätsgesetz ${}\left({\frac {p}{q}}\right)$ auf ${}\left({\frac {q}{p}}\right)$ zurückführen. In beiden Fällen kommt man also auf eine Situation, wo ${}\left({\frac {k}{q}}\right)$ zu berechnen ist, wo ${}q$ eine ungerade Primzahl ist und ${}k<q$ beliebig.

Es sei ${}k=2^{\alpha }\cdot p_{1}^{\alpha _{1}}\cdots p_{r}^{\alpha _{r}}$ die Primfaktorzerlegung von ${}k$. Dann ist nach der Multiplikativität des Legendre-Symbols

${}\left({\frac {k}{q}}\right)=\left({\frac {2^{\alpha }}{q}}\right)\cdot \left({\frac {p_{1}^{\alpha _{1}}}{q}}\right)\cdots \left({\frac {p_{r}^{\alpha _{r}}}{q}}\right)=\left({\frac {2}{q}}\right)^{\alpha }\cdot \left({\frac {p_{1}}{q}}\right)^{\alpha _{1}}\cdots \left({\frac {p_{r}}{q}}\right)^{\alpha _{r}}\,.$

Jetzt kann ${}\left({\frac {2}{q}}\right)$ nach dem zweiten Ergänzungsgesetz berechnet und die ${}\left({\frac {p_{i}}{q}}\right)$ können für ${}i=1,\ldots ,r$ nach dem gleichen Verfahren auf die Berechnung von ${}\left({\frac {q}{p_{i}}}\right)$ zurückgeführt werden (von den Exponenten ${}\alpha ,\alpha _{i}$ 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, sodass man schließlich das Resultat erhält.

Beispiel Referenznummer erstellen

Man möchte entscheiden, ob die Gleichung

${}x^{2}=10\mod 13\,$

eine Lösung besitzt. Dazu berechnet man

${}\left({\frac {10}{13}}\right)=\left({\frac {2}{13}}\right)\left({\frac {5}{13}}\right)\,.$

Der erste Faktor

$\left({\frac {2}{13}}\right)$

lässt sich mit Hilfe des zweiten Ergänzungssatzes zu ${}-1$ bestimmen, weil ${}13\mod 8=5$ und ${}p=5\mod 8$ ergibt das Vorzeichen ${}-1$.

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

${}\left({\frac {5}{13}}\right)=+\left({\frac {13}{5}}\right)\,,$

weil ${}5\mod 4=1$ gilt (der Rest ${}13\mod 4$ braucht gar nicht mehr berechnet zu werden, da es ausreicht, dass hier ${}5$ oder ${}13$ modulo ${}4$ den Rest ${}1$ lässt, damit das Vorzeichen ${}+$ ist). Jetzt nutzt man aus, dass ${}13=3\mod 5$ ist. Man schreibt:

${}\left({\frac {13}{5}}\right)=\left({\frac {3}{5}}\right)\,.$

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

${}\left({\frac {3}{5}}\right)=\left({\frac {5}{3}}\right)=\left({\frac {2}{3}}\right)=-1\,,$

da ${}5\mod 4=1$ ist und da ${}2=-1$ kein Quadrat modulo ${}3$ ist.

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

${}\left({\frac {10}{13}}\right)=\left({\frac {2}{13}}\right)\left({\frac {5}{13}}\right)=\left(-1\right)\cdot \left(-1\right)=1\,.$

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

Beispiel Referenznummer erstellen

Man möchte entscheiden, ob die Gleichung

$x^{2}=57\mod 127$

eine Lösung besitzt. Dazu berechnet man

${}\left({\frac {57}{127}}\right)=\left({\frac {3}{127}}\right)\left({\frac {19}{127}}\right)\,$

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

${}\left({\frac {3}{127}}\right)=-\left({\frac {127}{3}}\right)=-\left({\frac {1}{3}}\right)=-1\,$

und

${}{\begin{aligned}\left({\frac {19}{127}}\right)&=-\left({\frac {127}{19}}\right)\\&=-\left({\frac {13}{19}}\right)\\&=-\left({\frac {19}{13}}\right)\\&=-\left({\frac {6}{13}}\right)\\&=(-1)\left({\frac {2}{13}}\right)\left({\frac {3}{13}}\right)\\&=(-1)(-1)\left({\frac {13}{3}}\right)\\&=(-1)(-1)\left({\frac {1}{3}}\right)\\&=(-1)(-1)1\\&=1.\end{aligned}}$

Setzt man alles zusammen, so ergibt sich

${}\left({\frac {57}{127}}\right)=-1\,$

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 ${}n$ und eine ganze Zahl ${}k$ definiert man das Jacobi-Symbol, geschrieben ${}\left({\frac {k}{n}}\right)$ (${}k$ nach ${}n$), wie folgt. Es sei ${}n=p_{1}\cdots p_{r}$ die Primfaktorzerlegung von ${}n$. Dann setzt man

${}\left({\frac {k}{n}}\right):=\left({\frac {k}{p_{1}}}\right)\cdots \left({\frac {k}{p_{r}}}\right)\,.$

Carl Gustav Jacob Jacobi (1804-1851)

Im Fall ${}n=p$ 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 ${}1$, wenn ${}k$ ein Quadrat modulo ${}n$ ist. Die Definition des Jacobi-Symbols nimmt Bezug auf die Primfaktorzerlegung von ${}n$, 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

Es seien ${}k,k_{1},k_{2}$ ganze Zahlen und seien ${}n,n_{1},n_{2}$ ungerade positive Zahlen. Dann gelten folgende Aussagen.

1. Das Jacobi-Symbol ${}\left({\frac {k}{n}}\right)$ hängt nur vom Rest ${}k\mod n$ ab.
2. Es ist ${}\left({\frac {k_{1}k_{2}}{n}}\right)=\left({\frac {k_{1}}{n}}\right)\left({\frac {k_{2}}{n}}\right)$.
3. Es ist ${}\left({\frac {k}{n_{1}n_{2}}}\right)=\left({\frac {k}{n_{1}}}\right)\left({\frac {k}{n_{2}}}\right)$.

Beweis

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

$\Box$

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

Satz

Es seien ${}n$ und ${}m$ positive ungerade Zahlen. Dann gelten folgende Aussagen.

1. ${}\left({\frac {m}{n}}\right)\left({\frac {n}{m}}\right)=(-1)^{{\frac {n-1}{2}}{\frac {m-1}{2}}}$.
2. ${}\left({\frac {-1}{n}}\right)=(-1)^{(n-1)/2}$.
3. ${}\left({\frac {2}{n}}\right)=(-1)^{(n^{2}-1)/8}$.

Beweis

Diese Aussagen werden in den Aufgaben bewiesen.

$\Box$

Bemerkung   Referenznummer erstellen

Es seien ${}n$ und ${}m$ ungerade verschiedene Zahlen, und man möchte das Jacobi-Symbol ${}\left({\frac {n}{m}}\right)$ berechnen (man berechnet im Allgemeinen nicht, ob ${}n$ ein quadratischer Rest modulo ${}m$ ist, dies ist nur dann der Fall, wenn ${}m$ eine Primzahl ist). Durch die Restberechnung ${}n\mod m$ können wir sofort annehmen, dass ${}n<m$ ist. Wir schreiben

${}n=2^{\alpha }k\,,$

wobei ${}k$ ungerade sei. Dann gilt nach Lemma 8.7

${}\left({\frac {n}{m}}\right)=\left({\frac {2^{\alpha }}{m}}\right)\cdot \left({\frac {k}{m}}\right)=\left({\frac {2}{m}}\right)^{\alpha }\cdot \left({\frac {k}{m}}\right)\,.$

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

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

<< | Kurs:Zahlentheorie (Osnabrück 2016-2017) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)