Kurs:Zahlentheorie (Osnabrück 2016-2017)/Vorlesung 8/latex
\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
\mavergleichskette
{\vergleichskette
{ 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}
{}
{
\faktsituation {Es sei $p$ eine ungerade
\definitionsverweis {Primzahl}{}{}
und
\mavergleichskette
{\vergleichskette
{ k
}
{ \in }{ \Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
kein Vielfaches von $p$.}
\faktuebergang {Dann gelten folgende Aussagen.}
\faktfolgerung {\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)}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
\aufzaehlungdreibeweis{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
\mavergleichskettek
{\vergleichskettek
{ 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.
}{Es 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 mit
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
\mavergleichskettealign
{\vergleichskettealign
{ \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 {Es seien
\mathkor {} {p} {und} {q} {}
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 {}
}
{
Es sei
\mavergleichskette
{\vergleichskette
{ t
}
{ = }{ { \frac{ p-1 }{ 2 } }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ 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)}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
sodass 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. Es ist ferner
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{ qi-pj
}
{ > }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
genau dann, wenn
\mavergleichskettedisp
{\vergleichskette
{ { \frac{ qi }{ p } }
}
{ >} { j
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist, was genau für
\mavergleichskette
{\vergleichskette
{ 1
}
{ \leq }{ j
}
{ = }{ \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
{}
{
Es 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
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{ k
}
{ < }{ q
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
beliebig.
Es sei
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{ i
}
{ = }{ 1 , \ldots , r
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nach dem gleichen Verfahren auf die Berechnung von
\mathl{\left( \frac{ q }{ p_i }\right)}{} zurückgeführt werden
\zusatzklammer {von den Exponenten
\mathl{\alpha, \alpha_i}{} kommt es nur auf die Parität an} {} {.}
Bei diesem Verfahren werden natürlich die Nenner
\zusatzklammer {und damit auch die Zähler} {} {}
in den Legendre-Symbolen kleiner, sodass 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
\mavergleichskette
{\vergleichskette
{ 13
}
{ = }{ 5 \mod 8
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und dies das Vorzeichen $-1$ ergibt.
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
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{ 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/(13)}{} bestimmt
\zusatzklammer {
\mavergleichskettek
{\vergleichskettek
{ 13-6
}
{ = }{ 7
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {.}
}
\inputbeispiel{}
{
Man möchte entscheiden, ob die Gleichung
\mavergleichskettedisp
{\vergleichskette
{ 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 modulo einer Primzahl ist oder nicht, ohne die Primfaktorzerlegungen der Zahlen, die bei der sukzessiven Anwendung des Reziprozitätsgesetzes auftreten, 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)}{}
\zusatzklammer {$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]{ \bildeinlesungjpg {Carl_Jacobi} {jpg} }
\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
\mavergleichskette
{\vergleichskette
{ n
}
{ = }{ p
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine ungerade Primzahl ist das Jacobi-Symbol nichts anderes als das Legendre-Symbol, wobei der Fall, dass $k$ nicht teilerfremd zu $n$ ist, ausdrücklich erlaubt ist. 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}
{}
{
Es 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
\mavergleichskette
{\vergleichskette
{ \left( \frac{ k_1 k_2 }{ n }\right)
}
{ = }{ \left( \frac{ k_1 }{ n }\right) \left( \frac{ k_2 }{ n }\right)
}
{ }{
}
{ }{
}
{ }{}
}
{}{}{.}
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{ \left( \frac{ k }{ n_1 n_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.
{Restklassenringe (Z)/Quadratisches Reziprozitätsgesetz/Jacobi/Fakt}
{Satz}
{}
{
\faktsituation {Es seien $n$ und $m$ positive ungerade Zahlen.}
\faktuebergang {Dann gelten folgende Aussagen.}
\faktfolgerung {\aufzaehlungdrei{
\mavergleichskette
{\vergleichskette
{ \left( \frac{ m }{ n }\right) \left( \frac{ n }{ m }\right)
}
{ = }{ (-1)^{\frac{n-1}{2}\frac{m-1}{2} }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{
\mavergleichskette
{\vergleichskette
{ \left( \frac{ -1 }{ n }\right)
}
{ = }{ (-1)^{(n-1)/2}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{
\mavergleichskette
{\vergleichskette
{ \left( \frac{ 2 }{ n }\right)
}
{ = }{ (-1)^{(n^2-1)/8}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
Diese Aussagen werden in den Aufgaben bewiesen.
\inputbemerkung
{}
{
Es seien $n$ und $m$ ungerade verschiedene Zahlen, und man möchte das
\definitionsverweis {Jacobi-Symbol}{}{}
\mathl{\left( \frac{ n }{ m }\right)}{} berechnen
\zusatzklammer {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
\mavergleichskette
{\vergleichskette
{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, 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) | >> |
|---|