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
\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}
{}
{
Es 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
\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 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 {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 {}
}
{
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)}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
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
\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
\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.
Es 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.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
\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}
{}
{
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
\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.
{Restklassenringe (Z)/Quadratisches Reziprozitätsgesetz/Jacobi/Fakt}
{Satz}
{}
{
Es 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
{}
{
Es 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
\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, 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) | >> |
|---|