Kurs:Zahlentheorie (Osnabrück 2016-2017)/Vorlesung 7/latex
\setcounter{section}{7}
\zwischenueberschrift{Quadratische Reste modulo einer Primzahl}
Modulo $2$ ist jede Zahl ein quadratischer Rest. Für ungerade Primzahlen kann man ebenfalls sofort eine Aussage über die Anzahl der Quadratreste machen.
\inputfaktbeweis
{Restklassenringe (Z)/Quadratreste/Anzahl/Fakt}
{Satz}
{}
{
Es sei $p$ eine ungerade Primzahl. Dann gibt es
\mathl{\frac{p+1}{2}}{} quadratische Reste modulo $p$ und
\mathl{\frac{p-1}{2}}{} nichtquadratische Reste modulo $p$.
}
{
Zunächst ist $0$ ein quadratischer Rest. Wir betrachten im folgenden nur noch die Einheiten in
\mathl{\Z/(p)}{}
\zusatzklammer {also die von $0$ verschiedenen Reste} {} {}
und zeigen, dass es darunter gleich viele quadratische und nichtquadratische Reste gibt. Die Abbildung
\maabbeledisp {} { { \left( \Z/(p) \right) }^{\times} } { { \left( \Z/(p) \right) }^{\times}
} {x} { x^2
} {,}
ist offenbar ein Gruppenhomomorphismus der Einheitengruppe in sich selbst. Ein Element
\mathl{k \in (\Z/(p))^\times}{} ist genau dann ein Quadratrest, wenn es im Bild dieses Homomorphismus liegt. Nach dem Isomorphiesatz ist \anfuehrung{Bild = Urbild modulo Kern}{,} sodass wir den Kern bestimmen müssen. Der Kern besteht aus allen Elementen $x$ mit
\mavergleichskette
{\vergleichskette
{ x^2
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Dazu gehören
\mathkor {} {1} {und} {-1} {,}
und diese beiden Elemente sind verschieden, da $p$ ungerade ist. Aus der polynomialen Identität
\mavergleichskette
{\vergleichskette
{ x^2-1
}
{ = }{(x+1)(x-1)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt, dass es keine weiteren Lösungen geben kann. Der Kern besteht also aus genau $2$ Elementen und damit besteht das Bild aus
\mathl{{ \frac{ p-1 }{ 2 } }}{} Elementen.
\inputbemerkung
{}
{
Wenn zu einer Primzahl $p$ eine
\definitionsverweis {primitive Einheit}{}{}
\mathl{g \in { \left( \Z/(p) \right) }^{\times}}{} vorliegt, so hat man einen Gruppenisomorphismus
\maabbeledisp {} { { \left( \Z/(p-1) ,0,+ \right) } } { { \left( { \left( \Z/(p) \right) }^{\times} ,1, \cdot \right) }
} {i} { g^i
} {.}
Dabei entsprechen die Quadrate rechts denjenigen Elementen links, die ein Vielfaches der $2$ sind. Bei $p$ ungerade besitzt die Hälfte der Elemente links diese Eigenschaft. Insbesondere ist ein Element
\mathl{k \in { \left( \Z/(p) \right) }^{\times}}{} genau dann ein Quadratrest, wenn es von der Form
\mavergleichskettedisp
{\vergleichskette
{k
}
{ =} {g^{2j}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist.
}
\inputdefinition
{}
{
Für eine ungerade Primzahl $p$ und eine zu $p$ teilerfremde Zahl
\mathl{k \in \Z}{} definiert man das \definitionswort {Legendre-Symbol}{,} geschrieben
\mathl{\left( \frac{ k }{ p }\right)}{}
\zusatzklammer {sprich \anfuehrung{$k$ nach $p$}{}} {} {,}
durch
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{ \left( \frac{ k }{ p }\right)
}
{ \defeq} {\begin{cases} 1, \text{ falls } k \text{ quadratischer Rest modulo } p \text{ ist}, \\
- 1, \text{ falls } k \text{ kein quadratischer Rest modulo } p \text{ ist}.
\end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
}
Insbesondere ist
\mavergleichskette
{\vergleichskette
{ \left( \frac{ k }{ p }\right)
}
{ = }{ \left( \frac{ k \mod p }{ p }\right)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Die Werte des Legendre-Symbols, also $1$ und $-1$, kann man dabei in $\Z$, in $\Z^\times$ oder in
\mathl{{ \left( \Z/(p) \right) }^{\times}}{} auffassen. Für Vielfache von $p$ definierte man manchmal das Legendre-Symbol ebenfalls, und zwar mit dem Wert $0$.
\inputfaktbeweis
{Restklassenringe (Z)/Quadratreste/Legendre ist multiplikativ/Fakt}
{Lemma}
{}
{
Es sei $p$ eine ungerade Primzahl. Dann ist die Abbildung \maabbeledisp {} { { \left( \Z/(p) \right) }^{\times} } { \{ \pm 1\} } {k} { \left( \frac{ k }{ p }\right) } {,} ein \definitionsverweis {Gruppenhomomorphismus}{}{.}
}
{
Die Quadrate bilden offenbar eine Untergruppe in der Einheitengruppe
\mathl{{ \left( \Z/(p) \right) }^{\times}}{,} die nach
Satz 7.1
den
\definitionsverweis {Index}{}{}
$2$ besitzt. Daher ist
\mavergleichskettedisp
{\vergleichskette
{ { \left( \Z/(p) \right) }^{\times}/\text{Quadrate}
}
{ \cong} { \Z/(2)
}
{ \cong} { \{\pm 1 \}
}
{ } {
}
{ } {
}
}
{}{}{}
und die Restklassenabbildung ist gerade die Abbildung auf das Legendre-Symbol.
Die folgende Aussage heißt das \stichwort {Euler-Kriterium} {} für quadratische Reste.
\inputfaktbeweis
{Restklassenringe (Z)/Quadratreste/Euler Kriterium/Fakt}
{Satz}
{}
{
Es sei $p$ eine ungerade Primzahl. Dann gilt für eine zu $p$ teilerfremde Zahl $k$ die Gleichheit
\mathdisp {\left(\frac{k}{p}\right) = k^{ \frac{p-1}{2} } \mod p} { . }
}
{
Es ist
\mavergleichskette
{\vergleichskette
{ { \left( k^{ \frac{p-1}{2} } \right) }^2
}
{ = }{k^{p-1}
}
{ = }{1
}
{ }{
}
{ }{
}
}
{}{}{}
nach
Lemma 4.6.
Daher ist
\mavergleichskettedisp
{\vergleichskette
{ k^{ \frac{p-1}{2} }
}
{ =} { \pm 1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Die Abbildung
\maabbeledisp {} { { \left( \Z/(p) \right) }^{\times} } {\{ \pm 1\}
} {k} { k^{\frac{p-1}{2} }
} {,}
ist
\zusatzklammer {wie jedes Potenzieren} {} {}
ein
\definitionsverweis {Gruppenhomomorphismus}{}{.}
Die Quadrate werden darunter auf $1$ abgebildet, da für
\mavergleichskette
{\vergleichskette
{ k
}
{ = }{ x^2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{ k^{ \frac{p-1}{2} }
}
{ =} { (x^2)^{ \frac{p-1}{2} }
}
{ =} { x^{p-1}
}
{ =} { 1
}
{ } {
}
}
{}{}{}
gilt. Da nach
Satz 5.11
die Einheitengruppe
\mathl{{ \left( \Z/(p) \right) }^{\times}}{} zyklisch ist, muss diese Abbildung surjektiv sein
\zusatzklammer {sonst hätte jedes Element eine kleinere Ordnung} {} {.}
Damit muss diese Abbildung mit der durch das Legendre-Symbol gegebenen übereinstimmen.
\zwischenueberschrift{Das Quadratische Reziprozitätsgesetz}
Seien $p$ und $q$ zwei ungerade Primzahlen. Dann kann $p$ ein quadratischer Rest modulo $q$ sein \zusatzklammer {oder nicht} {} {} und $q$ kann ein quadratischer Rest modulo $p$ sein, oder nicht. Das Quadratische Reziprozitätsgesetz, das von Euler entdeckt und von Gauß erstmals bewiesen wurde, behauptet nun, dass es einen direkten Zusammenhang zwischen diesen beiden Eigenschaften gibt. Es erlaubt weiterhin mit den beiden unten genannten Ergänzungssätzen algorithmisch zu entscheiden, ob eine Zahl ein quadratischer Rest oder ein nichtquadratischer Rest ist.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Carl_Friedrich_Gauss.jpg} }
\end{center}
\bildtext {Carl Friedrich Gauss (1777-1855)} }
\bildlizenz { Carl Friedrich Gauss.jpg } {} {Bcrowell} {Commons} {PD} {Ausschnitt aus einem Gemälde von Gottlieb Biermann, 1887}
{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 {}
}
{
Dies wird weiter unten nach einigen Vorbereitungen bewiesen. Die zweite Gleichung ist elementar.
In Worten: Wenn
\mathkor {} {p} {und} {q} {}
beide den Rest $3$ modulo $4$ haben, so ist $p$ modulo $q$ ein quadratischer Rest genau dann, wenn $q$ modulo $p$ ein nichtquadratischer Rest ist. In allen anderen Fällen ist $p$ modulo $q$ ein quadratischer Rest genau dann, wenn $q$ modulo $p$ ein quadratischer Rest ist.
\inputbeispiel{}
{
Betrachten wir die beiden Primzahlen
\mathkor {} {11} {und} {19} {,}
die beide modulo $4$ den Rest $3$ haben. Es ist
\mavergleichskette
{\vergleichskette
{19
}
{ = }{8
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
modulo $11$ und dies ist nach
Beispiel 6.4
kein Quadratrest. Gemäß
dem Reziprozitätsgesetz
muss also $11$ modulo $19$ ein quadratischer Rest sein. In der Tat ist
\mavergleichskettedisp
{\vergleichskette
{7^2
}
{ =} {49
}
{ =} {11 \mod 19
}
{ } {
}
{ } {
}
}
{}{}{.}
Betrachtet man hingegen die Primzahlen
\mathkor {} {11} {und} {13} {,}
so hat $11$ modulo $4$ den Rest $3$ und $13$ hat modulo $4$ den Rest $1$. Es ist
\mavergleichskette
{\vergleichskette
{13
}
{ = }{2 \mod 11
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein nichtquadratischer Rest, und daher ist auch $11$ ein nichtquadratischer Rest modulo $13$.
}
Die beiden folgenden Sätze werden die Ergänzungssätze zum quadratischen Reziprozitätsgesetz genannt, da sie klären, wann die $-1$ und wann die $2$ quadratische Reste sind. In der algorithmischen Bestimmung von Quadratresten sind diese beiden Fälle ebenfalls unerlässlich.
\inputfaktbeweis
{Quadratisches Reziprozitätsgesetz/Ergänzungssatz 1/Fakt}
{Satz}
{}
{
Für eine ungerade Primzahl $p$ gilt:
\mavergleichskettedisp
{\vergleichskette
{ \left( \frac{ -1 }{ p }\right)
}
{ =} { (-1)^{\frac{p-1}{2} }
}
{ =} { \begin{cases} 1 \, , \text{ falls } p = 1 \mod 4 \, ,\\ -1 \, , \text{ sonst } \text{(also bei } p = 3 \mod 4 \mbox{)} \, .\end{cases}
}
{ } {
}
{ } {
}
}
{}{}{}
}
{
{Quadratisches Reziprozitätsgesetz/Ergänzungssatz 2/Fakt}
{Satz}
{}
{
Für eine ungerade Primzahl $p$ gilt:
\mavergleichskettedisp
{\vergleichskette
{ \left(\frac{2}{p}\right)
}
{ =} {(-1)^{\frac{p^2-1}{8} }
}
{ =} { \left\{\begin{matrix}1 \, , &\mbox{falls} & p = \pm 1 \mod 8 \, , \\ -1&\mbox{sonst}&\mbox{(also }p = \pm 3 \mod8\mbox{)}&\, .\end{matrix}\right.
}
{ } {
}
{ } {
}
}
{}{}{}
}
{
Dies wird weiter unten bewiesen.
Die Elemente im Restklassenkörper
\mathl{\Z/(p)}{} werden meist durch die Zahlen von $0$ bis
\mathl{p-1}{} repräsentiert. Für das folgende Vorzeichenlemma von Gauß ist es sinnvoll, ein anderes Repräsentantensystem
\zusatzklammer {für die von $0$ verschiedenen Elemente} {} {}
zu fixieren. Wir setzen $t=\frac{p-1}{2}$ und
\mathdisp {S=S_{-} \cup S_+ \text{ mit } S_{-} = \{ - t , -t+1 , \ldots , -2,-1\} \text{ und } S_{+} = \{ 1,2 , \ldots , t-1, t\}} { . }
Wir unterteilen also die Einheitengruppe in eine positive und eine negative Hälfte. Dieses Repräsentantensystem ist dadurch ausgezeichnet, dass jedes Element durch das betragmäßig kleinste Element repräsentiert wird. Im folgenden Lemma betrachtet man zu einer zu $p$ teilerfremden Zahl $k$ die Menge der Vielfachen
\mathbed {ik} {}
{i = 1, \ldots , t} {}
{} {} {} {,}
in
\mathl{\Z/(p)}{} und schaut, ob sie in der negativen oder der positiven Hälfte liegen. Man definiert die sogenannten \stichwort {Gaußschen Vorzeichen} {}
\mavergleichskettedisp
{\vergleichskette
{ \epsilon_i
}
{ =} {\epsilon_i (k)
}
{ =} { \begin{cases} 1, \text{ falls } ik \in S_+ \, , \\ -1, \text{ falls } ik \in S_- \, . \end{cases}
}
{ } {
}
{ } {
}
}
{}{}{}
\inputbeispiel{}
{
In
\mathl{\Z/(11)}{} ist
\mavergleichskette
{\vergleichskette
{S_+
}
{ = }{ \{1,2,3,4,5 \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{S_-
}
{ = }{ \{-1,-2,-3,-4,-5 \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Für
\mavergleichskette
{\vergleichskette
{k
}
{ = }{3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
muss man, um die Gaußschen Vorzeichen zu bestimmen, die ersten fünf Vielfachen berechnen und schauen, ob sie zur negativen oder zur positiven Hälfte gehören. Es ist
\mathdisp {3 \in S_+,\, 6=-5 \in S_-,\, 9 = -2 \in S_-,\, 12 =1 \in S_+,\, 15 =4 \in S_+} { , }
die Vorzeichen sind also der Reihe nach
\mathdisp {1,-1,-1,1,1} { . }
Ihr Produkt ist $1$, und mit
dem folgenden Gaußschen Vorzeichenlemma
folgt, dass $3$ ein Quadratrest ist. In der Tat ist
\mavergleichskette
{\vergleichskette
{3
}
{ = }{5^2 \mod 11
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
Die folgende Aussage heißt \stichwort {Gaußsches Vorzeichenlemma} {.}
\inputfaktbeweis
{Restklassenringe (Z)/Quadratreste/Gauß Vorzeichenlemma/Fakt}
{Lemma}
{}
{
Für eine ungerade
\definitionsverweis {Primzahl}{}{}
$p$ und eine zu $p$
\definitionsverweis {teilerfremde}{}{}
Zahl $k$ gilt mit den zuvor eingeführten Bezeichnungen
\mavergleichskettedisp
{\vergleichskette
{ \left( \frac{ k }{ p }\right)
}
{ =} { \epsilon_1 \cdot \epsilon_2 \cdots \epsilon_t
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
{
Es sei
\mathl{s_i \in S_+}{} durch die Bedingung
\mathdisp {i k =\epsilon_i s_i \mod p} { }
festgelegt. Wir betrachten alle Vielfachen $j k$,
\mathl{j \in S= (\Z/(p))^ \times}{.} Die Menge all dieser Vielfachen ist selbst ganz $S$, da ja $k$ eine Einheit und daher die Multiplikation mit $k$ eine Bijektion ist. Es ist
\mathl{(-i) k = -ik = - \epsilon_i s_i}{} für
\mathl{i \in S_+=\{1,\ldots, t\}}{.} Daher ist
\mathl{S_+ = \{1 , \ldots , t \} =\{s_1, \ldots ,s_t\}}{.} Deshalb gilt
\mathl{t! = \prod_{i=1}^t s_i}{} und somit
\mavergleichskettedisp
{\vergleichskette
{ t! k^t
}
{ =} { { \left( \prod_{i = 1}^t i \right) } { \left( \prod_{i = 1}^t k \right) }
}
{ =} { \prod_{i = 1}^t i k
}
{ =} { \prod_{i = 1}^t \epsilon_i s_i
}
{ =} { { \left( \prod_{i = 1}^t \epsilon_i \right) } { \left( \prod_{i = 1}^t s_i \right) }
}
}
{
\vergleichskettefortsetzung
{ =} { { \left( \prod_{i = 1}^t \epsilon_i \right) } t! \mod p
}
{ } {}
{ } {}
{ } {}
}{}{.}
Durch kürzen mit $t!$
\zusatzklammer {das ist eine Einheit} {} {}
ergibt sich
\mavergleichskettedisp
{\vergleichskette
{ k^t
}
{ =} { \prod_{i = 1}^t \epsilon_i \mod p
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
und
das Euler-Kriterium,
nämlich
\mavergleichskettedisp
{\vergleichskette
{ k^t
}
{ =} { k^{\frac{p-1}{2} }
}
{ =} { \left( \frac{ k }{ p }\right) \mod p
}
{ } {
}
{ } {
}
}
{}{}{,}
liefert das Ergebnis.
Mit dem Gaußschen Vorzeichenlemma beweisen wir zunächst den zweiten Ergänzungssatz zum quadratischen Reziprozitätsgesetz, der beschreibt, wann $2$ ein quadratischer Rest ist.
\inputfaktbeweis
{Quadratisches Reziprozitätsgesetz/Ergänzungssatz 2/Fakt}
{Satz}
{}
{
Für eine ungerade Primzahl $p$ gilt:
\mavergleichskettedisp
{\vergleichskette
{ \left(\frac{2}{p}\right)
}
{ =} {(-1)^{\frac{p^2-1}{8} }
}
{ =} { \left\{\begin{matrix}1 \, , &\mbox{falls} & p = \pm 1 \mod 8 \, , \\ -1&\mbox{sonst}&\mbox{(also }p = \pm 3 \mod8\mbox{)}&\, .\end{matrix}\right.
}
{ } {
}
{ } {
}
}
{}{}{}
}
{
Wir benutzen
Lemma 7.11
und haben zu bestimmen, wie viele der Zahlen
\mathbed {2i} {}
{i = 1 , \ldots , t = { \frac{ p-1 }{ 2 } }} {}
{} {} {} {,}
in $S_-$ liegen. Nun ist
\mathl{2i \in S_-}{} genau dann, wenn
\mavergleichskette
{\vergleichskette
{2 i
}
{ > }{ { \frac{ p-1 }{ 2 } }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\zusatzklammer {alle zu betrachtenden Vielfachen von $2$ sind kleiner als $p$} {} {.}
Dies ist äquivalent zu
\mavergleichskette
{\vergleichskette
{i
}
{ > }{ { \frac{ p-1 }{ 4 } }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und wir haben das kleinste $i$ mit dieser Eigenschaft zu finden. Ist
\mathl{p-1}{} ein Vielfaches von $4$, so ist
\mathl{{ \frac{ p-1 }{ 4 } } +1}{} das kleinste $i$ und insgesamt gibt es in diesem Fall
\mavergleichskettedisp
{\vergleichskette
{ { \frac{ p-1 }{ 2 } } - { \left( { \frac{ p-1 }{ 4 } } +1 \right) } +1
}
{ =} { { \frac{ p-1 }{ 4 } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
solche $i$. Diese Anzahl ist bei
\mathl{p=1 \mod 8}{} gerade und bei
\mathl{p=5 \mod 8}{} ungerade, was das Ergebnis in diesen Fällen ergibt.
Es sei also nun
\mathl{p=3,7 \mod 8}{} bzw.
\mathl{p= 3 \mod 4}{.} Dann ist das kleinste $i$ derart, dass
\mathl{2i > { \frac{ p-1 }{ 2 } }}{} ist, gleich
\mathl{{ \frac{ p-1 }{ 4 } } + { \frac{ 1 }{ 2 } }}{,} und es gibt insgesamt
\mavergleichskettedisp
{\vergleichskette
{ { \frac{ p-1 }{ 2 } } - { \left( { \frac{ p-1 }{ 4 } } + { \frac{ 1 }{ 2 } } \right) } +1
}
{ =} { { \frac{ p-1 }{ 4 } } + { \frac{ 1 }{ 2 } }
}
{ =} { { \frac{ p+1 }{ 4 } }
}
{ } {
}
{ } {
}
}
{}{}{}
solche $i$. Diese Anzahl ist bei
\mathl{p=3 \mod 8}{} ungerade und bei
\mathl{p=7 \mod 8}{} gerade, was die Behauptung in diesen Fällen ergibt.
| << | Kurs:Zahlentheorie (Osnabrück 2016-2017) | >> |
|---|