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

Aus Wikiversity
Zur Navigation springen Zur Suche springen

\setcounter{section}{8}






\zwischenueberschrift{Beweis des quadratischen Reziprozitätsgesetzes}

Im nächsten Lemma verwenden wir folgende Notation:

Zu einer ungeraden Primzahl $p$ und einer Zahl
\mathl{k \in \Z}{} sei
\mavergleichskettedisp
{\vergleichskette
{ S(k,p) }
{ =} { \sum_{i = 1} ^ \frac{p-1}{2} \left \lfloor \frac{ki}{p}\right\rfloor }
{ } { }
{ } { }
{ } { }
} {}{}{.}





\inputfaktbeweis
{Restklassenringe (Z)/Quadratreste/Beschreibung des Legendre Symbols mit Summe/Fakt}
{Lemma}
{}
{

Sei $p$ eine ungerade Primzahl und
\mathl{k \in \Z}{} kein Vielfaches von $p$. Dann gelten folgende Aussagen. \aufzaehlungdrei{ Es ist
\mavergleichskette
{\vergleichskette
{\epsilon_i }
{ = }{(-1)^\left \lfloor { \frac{ 2ki }{ p } } \right \rfloor }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} wobei $\epsilon_i$ wie im Gaußsches Vorzeichenlemma definiert ist. }{Es ist
\mavergleichskette
{\vergleichskette
{ \left( \frac{ k }{ p }\right) }
{ = }{ (-1)^{S(2k,p)} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} }{Ist $k$ ungerade, so ist
\mavergleichskette
{\vergleichskette
{ \left( \frac{ k }{ p }\right) }
{ = }{ (-1)^{S(k,p)} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} }

}
{

\aufzaehlungdrei{Zur Berechnung von
\mavergleichskette
{\vergleichskette
{\epsilon_i }
{ = }{ \epsilon_i(k) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} muss man bestimmen, ob der betragsmäßig kleinste Repräsentant von
\mavergleichskette
{\vergleichskette
{a }
{ = }{k i }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} in
\mathl{\Z/(p)}{} positiv oder negativ ist. Dies hängt davon ab, ob $a$ zu einem Intervall der Form
\mathl{[ \ell p, \ell p + { \frac{ p }{ 2 } } ]}{} oder der Form
\mathl{[ \ell p + { \frac{ p }{ 2 } } , ( \ell +1) p ]}{} gehört \zusatzklammer {wobei die Ränder wegen den Voraussetzungen unproblematisch sind} {} {.} Dies hängt davon ab, ob
\mathl{\left \lfloor { \frac{ 2 a }{ p } } \right \rfloor}{} gerade oder ungerade ist. }{Aus Teil (1) und dem Gaußschen Vorzeichenlemma folgt wegen \zusatzklammer {mit $t= \frac{p-1}{2}$} {} {}
\mavergleichskettedisp
{\vergleichskette
{ \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. }{Sei nun $k$ ungerade. Dann ist
\mathl{(p+k)/2}{} eine ganze Zahl. Unter Verwendung von Teil (2) erhält man
\mavergleichskettedisp
{\vergleichskette
{ \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
\mavergleichskettedisp
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{ \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
\mavergleichskettedisp
{\vergleichskette
{ \left( \frac{ 2 }{ p }\right) }
{ =} { (-1)^{\frac{(t+1)t}{2} } }
{ } { }
{ } { }
{ } { }
} {}{}{.} Man kann daher in der Gesamtgleichungskette
\mavergleichskettedisp
{\vergleichskette
{ \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. }

}


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





\inputfaktbeweis
{Quadratisches Reziprozitätsgesetz/Fakt}
{Satz}
{}
{

\faktsituation {Seien $p$ und $q$ zwei verschiedene ungerade \definitionsverweis {Primzahlen}{}{.}}
\faktuebergang {Dann gilt:}
\faktfolgerung {
\mavergleichskettedisp
{\vergleichskette
{ \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} }
{ } { }
{ } { }
} {}{}{}}
\faktzusatz {}
\faktzusatz {}

}
{

Sei
\mathl{t=\frac{p-1}{2}}{} und
\mathl{u=\frac{q-1}{2}}{.} Nach Lemma 8.1  (3) gilt
\mavergleichskette
{\vergleichskette
{ \left( \frac{ p }{ q }\right) \left( \frac{ q }{ p }\right) }
{ = }{ (-1)^{S(p,q) +S(q,p)} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} so dass also
\mavergleichskette
{\vergleichskette
{tu }
{ = }{ S(p,q) +S(q,p) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} zu zeigen ist. Betrachte
\mavergleichskettedisp
{\vergleichskette
{M }
{ =} {{ \left\{ qi-pj \mid 1 \leq i \leq t , \, 1 \leq j \leq u \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{.} Diese Menge besitzt $tu$ Elemente, und
\mathl{0 \not\in 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
\mathl{qi-pj>0}{} genau dann, wenn
\mathl{\frac{qi}{p} > j}{} ist, was genau für
\mathl{1 \leq j \leq \left \lfloor \frac{qi}{p} \right \rfloor}{} der Fall ist. Zu jedem
\mathbed {i} {}
{1 \leq i \leq t} {}
{} {} {} {,} gibt es also genau
\mathl{\left \lfloor \frac{qi}{p} \right \rfloor}{} Elemente in $M_+$. Damit hat $M_+$ genau
\mavergleichskettedisp
{\vergleichskette
{ \sum_{i = 1}^t \left \lfloor \frac{qi}{p} \right \rfloor }
{ =} { S(q,p) }
{ } { }
{ } { }
{ } { }
} {}{}{} Elemente. Die entsprechende Überlegung liefert, dass $M_-$ genau
\mathl{S(p,q)}{} Elemente besitzt, woraus
\mavergleichskettedisp
{\vergleichskette
{ tu }
{ =} { { \# \left( M \right) } }
{ =} { { \# \left( M_+ \right) } + { \# \left( M_- \right) } }
{ =} { S(q,p) + S(p,q) }
{ } { }
} {}{}{} folgt.

}


Das quadratische Reziprozitätsgesetz kann man auch so formulieren: Sind $p$ und $q$ zwei verschiedene ungerade Primzahlen, so gilt:
\mavergleichskettedisp
{\vergleichskette
{ \left( \frac{ p }{ q }\right) }
{ =} { \begin{cases}- \left( \frac{ q }{ p }\right) \, , \text{wenn} p \equiv q \equiv3 \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.






\inputbemerkung
{}
{

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

Sei
\mathl{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
\mavergleichskettedisp
{\vergleichskette
{\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
\mathl{\left(\frac{p_i}{q}\right)}{} können für
\mathl{i=1 , \ldots, r}{} nach dem gleichen Verfahren auf die Berechnung von
\mathl{\left(\frac{q}{p_i}\right)}{} zurückgeführt werden (von den Exponenten
\mathl{\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, so dass man schließlich das Resultat erhält.

}




\inputbeispiel{}
{

Man möchte entscheiden, ob die Gleichung
\mavergleichskettedisp
{\vergleichskette
{x^2 }
{ =} { 10 \mod 13 }
{ } { }
{ } { }
{ } { }
} {}{}{} eine Lösung besitzt. Dazu berechnet man
\mavergleichskettedisp
{\vergleichskette
{ \left(\frac{10}{13}\right) }
{ =} {\left(\frac{2}{13}\right) \left(\frac{5}{13}\right) }
{ } { }
{ } { }
{ } { }
} {}{}{.} Der erste Faktor
\mathdisp {\left(\frac{2}{13}\right)} { }
lässt sich mit Hilfe des zweiten Ergänzungssatzes zu $-1$ bestimmen, weil
\mathl{13 \mod 8 = 5}{} und
\mathl{p = 5 \mod 8}{} ergibt das Vorzeichen $-1$.

Um den zweiten Faktor zu berechnen, wendet man das Reziprozitätsgesetz an:
\mavergleichskettedisp
{\vergleichskette
{ \left(\frac{5}{13}\right) }
{ =} { + \left(\frac{13}{5}\right) }
{ } { }
{ } { }
{ } { }
} {}{}{,} weil
\mathl{5 \mod 4 = 1}{} gilt \zusatzklammer {der Rest
\mathl{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
\mathl{13 = 3 \mod 5}{} ist. Man schreibt:
\mavergleichskettedisp
{\vergleichskette
{ \left(\frac{13}{5}\right) }
{ =} { \left(\frac{3}{5}\right) }
{ } { }
{ } { }
{ } { }
} {}{}{.} Wiederum wendet man hier das Quadratische Reziprozitätsgesetz an: Es ist
\mavergleichskettedisp
{\vergleichskette
{ \left(\frac{3}{5}\right) }
{ =} {\left(\frac{5}{3}\right) }
{ =} { \left(\frac{2}{3}\right) }
{ =} { -1 }
{ } { }
} {}{}{,} da
\mavergleichskette
{\vergleichskette
{ 5 \mod 4 }
{ = }{ 1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ist und da
\mavergleichskette
{\vergleichskette
{2 }
{ = }{-1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} kein Quadrat modulo $3$ ist.

Setzt man nun beide Faktoren zusammen, so ergibt sich folgendes Resultat:
\mavergleichskettedisp
{\vergleichskette
{ \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 \zusatzklammer {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
\mathl{Z \mod 13}{} bestimmt \zusatzklammer {\mathlk{13 - 6 = 7}{}} {} {}


}




\inputbeispiel{}
{

Man möchte entscheiden, ob die Gleichung
\mathdisp {x^2 = 57 \mod 127} { }
eine Lösung besitzt. Dazu berechnet man
\mavergleichskettedisp
{\vergleichskette
{ \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:
\mavergleichskettedisp
{\vergleichskette
{ \left(\frac{3}{127}\right) }
{ =} { - \left(\frac{127}{3}\right) }
{ =} { - \left(\frac{1}{3}\right) }
{ =} { -1 }
{ } { }
} {}{}{} und
\mavergleichskettealign
{\vergleichskettealign
{ \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) }
} {
\vergleichskettefortsetzungalign
{ =} { (-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 }
} {
\vergleichskettefortsetzungalign
{ =} { 1 }
{ } {}
{ } {}
{ } {}
}{.} Setzt man alles zusammen, so ergibt sich
\mavergleichskettedisp
{\vergleichskette
{ \left(\frac{57}{127}\right) }
{ =} { -1 }
{ } { }
{ } { }
{ } { }
} {}{}{} und damit die Erkenntnis, dass die obige Gleichung keine Lösung besitzt.


}






\zwischenueberschrift{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.




\inputdefinition
{}
{

Für eine ungerade Zahl $n$ und eine ganze Zahl $k$ definiert man das \definitionswort {Jacobi-Symbol}{,} geschrieben
\mathl{\left(\frac{k}{n}\right)}{} ($k$
\definitionswortteil{nach}{} $n$), wie folgt. Es sei
\mavergleichskette
{\vergleichskette
{n }
{ = }{p_1 \cdots p_r }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die Primfaktorzerlegung von $n$. Dann setzt man
\mavergleichskettedisp
{\vergleichskette
{ \left(\frac{k}{n}\right) }
{ \defeq} {\left(\frac{k}{p_1}\right) \cdots \left(\frac{k}{p_r}\right) }
{ } { }
{ } { }
{ } { }
} {}{}{.}

}






\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Carl_Jacobi.eps} }
\end{center}
\bildtext {Carl Gustav Jacob Jacobi (1804-1851)} }

\bildlizenz { Carl Jacobi.jpg } {} {Stern} {Commons} {PD} {http://www.sil.si.edu/digitalcollections/hst/scientific-identity/explore.htm}


Im Fall
\mathl{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
\betonung{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.





\inputfaktbeweis
{Restklassenringe (Z)/Quadratische Reste/Jacobi-Symbol/Eigenschaften/Fakt}
{Lemma}
{}
{

Seien
\mathl{k, k_1, k_2}{} ganze Zahlen und seien
\mathl{n,n_1,n_2}{} ungerade positive Zahlen. Dann gelten folgende Aussagen. \aufzaehlungdrei{Das Jacobi-Symbol
\mathl{\left(\frac{k}{n}\right)}{} hängt nur vom Rest
\mathl{k \mod n}{} ab. }{Es ist
\mathl{\left(\frac{k_1 k_2 }{n}\right) = \left(\frac{k_1}{n}\right) \left(\frac{k_2 }{n}\right)}{.} }{Es ist
\mathl{\left(\frac{k}{n_1n_2}\right) = \left(\frac{k}{n_1}\right) \left(\frac{k}{n_2}\right)}{.} }

}
{

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.

\inputfaktbeweis
{Restklassenringe (Z)/Quadratisches Reziprozitätsgesetz/Jacobi/Fakt}
{Satz}
{}
{

Seien $n$ und $m$ positive ungerade Zahlen. Dann gelten folgende Aussagen. \aufzaehlungdrei{
\mathl{\left(\frac{m}{n}\right)\left(\frac{n}{m}\right)=(-1)^{\frac{n-1}{2}\frac{m-1}{2} }}{.} }{
\mathl{\left(\frac{-1}{n}\right) = (-1)^{(n-1)/2}}{.} }{
\mathl{\left(\frac{2}{n}\right) = (-1)^{(n^2-1)/8}}{.} }

}
{

Diese Aussagen werden in den Aufgaben bewiesen.

}







\inputbemerkung
{}
{

Seien $n$ und $m$ ungerade verschiedene Zahlen, und man möchte das Jacobi-Symbol
\mathl{\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
\mathl{n \mod m}{} können wir sofort annehmen, dass
\mathl{n < m}{} ist. Wir schreiben
\mavergleichskettedisp
{\vergleichskette
{n }
{ =} { 2^\alpha k }
{ } { }
{ } { }
{ } { }
} {}{}{,} wobei $k$ ungerade sei. Dann gilt nach Lemma 8.7
\mavergleichskettedisp
{\vergleichskette
{\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 \zusatzklammer {und der Ergänzungssätze} {} {,}
\mathl{\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 \zusatzklammer {und damit auch die Zähler} {} {} in den Jacobi-Symbolen kleiner, so dass 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)