Kurs:Zahlentheorie (Osnabrück 2016-2017)/Vorlesung 6/latex
\setcounter{section}{6}
\zwischenueberschrift{Der Charakterisierungssatz für zyklische Einheitengruppen}
Wir beenden zunächst unsere Überlegungen, wann die Einheitengruppe eines Restklassenringes von $\Z$ zyklisch ist.
\inputfaktbeweis
{Restklassenring (Z)/Einheitengruppe/p ist zwei/Nicht zyklisch/Fakt}
{Lemma}
{}
{
Die
\definitionsverweis {Einheitengruppe}{}{}
von
\mathl{\Z/(2^r)}{} ist nicht
\definitionsverweis {zyklisch}{}{}
für
\mavergleichskette
{\vergleichskette
{r
}
{ \geq }{3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
{
Bei
\mavergleichskette
{\vergleichskette
{r
}
{ = }{3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist dies eine direkte Berechnung. Generell ist für
\mavergleichskette
{\vergleichskette
{r
}
{ \geq }{3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Abbildung
\maabbdisp {} { { \left( \Z/(2^r) \right) }^{\times} } { { \left( \Z/(8) \right) }^{\times}
} {}
surjektiv
\zusatzklammer {da genau die ungeraden Elemente die Einheiten sind} {} {.}
Da eine Restklassengruppe einer zyklischen Gruppe wieder zyklisch ist, folgt, dass
\mathl{{ \left( \Z/(2^r) \right) }^{\times}}{} nicht zyklisch sein kann.
Unser abschließendes Resultat ist nun der folgende Satz.
\inputfaktbeweis
{Restklassenring (Z)/Einheitengruppe/Charakterisierung zyklisch/Fakt}
{Satz}
{}
{
Die
\definitionsverweis {Einheitengruppe}{}{}
\mathl{{ \left( \Z/(n) \right) }^{\times}}{} ist genau dann
\definitionsverweis {zyklisch}{}{,}
wenn
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {1,2,4,p^s,2p^s
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist, wobei $p$ eine ungerade Primzahl und
\mathl{s \geq 1}{} ist.
}
{
In den beschriebenen Fällen ist die Einheitengruppe
\mathl{\Z/(n) ^{\times}}{}
\definitionsverweis {zyklisch}{}{}
aufgrund von
Satz 5.11,
Bemerkung 5.12
und der Isomorphie
\mavergleichskettedisp
{\vergleichskette
{ { \left( \Z/(2p^r) \right) }^{\times}
}
{ \cong} { { \left( \Z/(2) \right) }^{\times} \times { \left( \Z/(p^r) \right) }^{\times}
}
{ \cong} { { \left( \Z/(p^r) \right) }^{\times}
}
{ } {
}
{ } {
}
}
{}{}{.}
Es sei also umgekehrt $n$ mit der Eigenschaft gegeben, dass
\mathl{{ \left( \Z/(n) \right) }^{\times}}{} zyklisch sei. Es sei
\mavergleichskette
{\vergleichskette
{ n
}
{ = }{ 2^r \cdot p_1^{r_1} \cdot p_2^{r_2} \cdots p_k^{r_k}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die kanonische Primfaktorzerlegung mit ungeraden Primzahlen
\mathl{p_1 , \ldots , p_k}{} und
\mavergleichskette
{\vergleichskette
{ r_i
}
{ \geq }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die nach dem Chinesischen Restsatz zur Isomorphie
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{ { \left( \Z/(n) \right) }^{\times}
}
{ =} { { \left( \Z/( 2^{r} ) \right) }^{\times} \times { \left( \Z/( p_1^{r_1} ) \right) }^{\times} \times { \left( \Z/( p_2^{r_2} ) \right) }^{\times} \times \cdots \times { \left( \Z/( p_k^{r_k} ) \right) }^{\times}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
führt. Da Restklassengruppen von zyklischen Gruppen wieder zyklisch sind, folgt nach
Lemma 6.1,
dass
\mavergleichskette
{\vergleichskette
{ r
}
{ = }{ 0,1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder $2$ ist. Ein Produkt von zyklischen Gruppen ist nur dann zyklisch, wenn die beteiligten Ordnungen paarweise teilerfremd sind. Die Ordnungen von
\mathl{{ \left( \Z/( p_i^{r_i} ) \right) }^{\times}}{} sind aber gerade für $p_i$ ungerade und
\mavergleichskette
{\vergleichskette
{ r_i
}
{ \geq }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
und die Ordnung von
\mathl{{ \left( \Z/( 2^{r} ) \right) }^{\times}}{} ist gerade für
\mavergleichskette
{\vergleichskette
{ r
}
{ \geq }{ 2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Also ist
\mavergleichskette
{\vergleichskette
{ k
}
{ \leq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Bei
\mavergleichskette
{\vergleichskette
{ k
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{ r
}
{ = }{ 2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nicht möglich. Bei
\mavergleichskette
{\vergleichskette
{ k
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
verbleiben die angeführten Fälle
\mavergleichskette
{\vergleichskette
{ n
}
{ = }{ 1,2,4
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
\zwischenueberschrift{Quadratische Reste}
Wir wollen nun wissen, welche Zahlen $k$ modulo einer fixierten Zahl $n$ \zusatzklammer {häufig einer Primzahl} {} {} ein Quadrat sind, also eine Quadratwurzel besitzen. Man spricht von quadratischen Resten und nichtquadratischen Resten \zusatzklammer {häufig wird auch von quadratischen Nichtresten gesprochen} {} {.}
\inputdefinition
{}
{
Eine ganze Zahl $k$ heißt \definitionswort {quadratischer Rest}{} modulo $n$, wenn es eine Zahl $x$ mit
\mavergleichskettedisp
{\vergleichskette
{x^2
}
{ =} { k \mod n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gibt. Im anderen Fall heißt $k$ ein \definitionswort {nichtquadratischer Rest}{} modulo $n$.
}
Eine Quadratzahl ist natürlich auch ein quadratischer Rest modulo jeder Zahl $n$. Umgekehrt ist eine Zahl, die selbst keine Quadratzahl ist, modulo gewisser Zahlen ein quadratischer Rest und modulo gewisser Zahlen ein nichtquadratischer Rest. Grundsätzlich kann man zu gegebenen $k$ und $n$ naiv testen, ob $k$ ein quadratischer Rest ist oder nicht, indem man alle Reste quadriert und schaut, ob der durch $k$ definierte Rest dabei ist. Die Frage nach den Quadratresten weist aber eine Reihe von Gesetzmäßigkeiten auf, die wir im folgenden kennenlernen werden und mit deren Hilfe man effektiver entscheiden kann, ob ein Quadratrest vorliegt oder nicht.
\inputbeispiel{}
{
In
\mathl{\Z/(11)}{} sind die Zahlen
\mathl{0,1,4,9,16=5,25=3}{} Quadratreste, die Zahlen
\mathl{2,6,7,8,10}{} sind nichtquadratische Reste.
}
\inputfaktbeweis
{Restklassenringe (Z)/Quadratreste/Chinesischer Restsatz und Reduktion/Fakt}
{Satz}
{}
{
Es sei $n$ eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung
\mathl{n= p_1^{r_1} \cdot p_2^{r_2} \cdots p_s^{r_s}}{}
\zusatzklammer {die $p_i$ seien also verschieden} {} {.}
Dann ist $k$ genau dann Quadratrest modulo $n$, wenn $k$ Quadratrest modulo
\mathl{p_i^{r_i}}{} ist für alle
\mathl{i=1 , \ldots , s}{.}
}
{
Dies folgt unmittelbar aus Satz 4.13.
\inputfaktbeweis
{Restklassenringe (Z)/Quadratreste/Ungerade Primzahlpotenz/Reduktion/Fakt}
{Satz}
{}
{
Es sei $p$ eine ungerade Primzahl und sei
\mathl{k \in \Z/(p^r)}{.}
\aufzaehlungzwei {Ist $k$ teilerfremd zu $p$
\zusatzklammer {also kein Vielfaches von $p$} {} {,}
dann ist $k$ genau dann ein Quadratrest modulo $p^r$, wenn $k$ ein Quadratrest modulo $p$ ist.
} {Ist
\mavergleichskette
{\vergleichskette
{k
}
{ = }{p^s u
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit $u$ teilerfremd zu $p$ und
\mathl{s<r}{,} so ist $k$ genau dann ein Quadratrest modulo $p^r$, wenn $s$ gerade und wenn $u$ ein Quadratrest modulo $p$ ist.}
}
{
Die natürliche Abbildung
\maabbdisp {} { \Z/(p^r) } { \Z/(p)
} {}
liefert sofort, dass ein Quadratrest modulo $p^r$ auch ein Quadratrest modulo $p$ ist. Wir zeigen zunächst die Umkehrung für Einheiten. Nach
Lemma 5.9
ist die Abbildung
\maabbdisp {} { { \left( \Z/(p^r) \right) }^{\times} } { { \left( \Z/(p) \right) }^{\times}
} {}
surjektiv und nach
Satz 5.11
sind die beteiligten Gruppen zyklisch. D.h. ein Erzeuger wird auf einen Erzeuger abgebildet. Insbesondere kann man diese Gruppen so mit additiven zyklischen Gruppen identifizieren, dass der Homomorphismus die den additiven Erzeuger $1$ auf die $1$ schickt. Dies erreicht man, indem man im folgenden kommutativen Diagramm die Identifikation links mit einem primitiven Element
\mathl{g \in \Z/(p^r)}{} und rechts ebenfalls mit $g$
\zusatzklammer {jetzt aufgefasst in \mathlk{\Z/(p)}{}} {} {}
stiftet.
\mathdisp {\begin{matrix} (\Z/(p^r))^\times & \longrightarrow & (\Z/(p))^\times \\ {\cong} \uparrow & & \uparrow {\cong} \\
\Z/(p^{r-1}(p-1)) & \longrightarrow & \Z/(p-1) \end{matrix}} { . }
Wir schreiben die untere horizontale Abbildung, unter Verwendung
des Chinesischen Restsatzes,
als
\mathdisp {\Z/(p^{r-1} ) \times \Z/(p-1 ) \cong \Z/(p^{r-1}(p-1) ) \longrightarrow \Z/(p-1 ) \text{ mit } 1 = (1,1) \longmapsto 1} { . }
Da überdies $p$ und
\mathl{p-1}{} teilerfremd sind, liegt hier insgesamt einfach die Projektion
\mathl{(b_1,b_2) \mapsto b_2}{} vor.
Die Voraussetzung, dass $k$ modulo $p$ ein Quadratrest ist, übersetzt sich dahingehend, dass das $k$ entsprechende Element
\zusatzklammer {sagen wir
\mathl{b=(b_1,b_2)}{}} {} {}
in
\mathl{\Z/(p-1)}{} ein Vielfaches von $2$ ist. D.h. die zweite Komponente, also $b_2$, ist ein Vielfaches der $2$. Da modulo der ungeraden Zahl
\mathl{p^{r-1}}{} jede Zahl ein Vielfaches von $2$ ist
\zusatzklammer {da $2$ eine Einheit in
\mathl{\Z/(p^{r-1})}{} ist} {} {,}
ist auch die erste Komponente, also $b_1$, ein Vielfaches von $2$ und so muss $b$ insgesamt ein Vielfaches der $2$ sein.
Es sei nun
\mathl{k=p^s u}{,}
\mathl{1 \leq s \leq r-1}{,} und zunächst angenommen, dass $k$ ein Quadrat ist. D.h wir können $k$ als
\mavergleichskette
{\vergleichskette
{k
}
{ = }{x^2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{x
}
{ = }{ p^t v
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
schreiben, wobei $v$ eine Einheit sei. Es ist also
\mavergleichskette
{\vergleichskette
{ p^s u
}
{ = }{ p^{2t} v^2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in
\mathl{\Z/(p^r)}{} und es ist
\mathl{2t <r}{} (sonst steht hier $0$). Durch Betrachten modulo
\mathl{p^s}{} und modulo
\mathl{p^{2t}}{} sieht man, dass
\mathl{s=2t}{} sein muss. Insbesondere ist $s$ gerade. Es gilt also
\mathl{p^su=p^sv^2 \mod p^r}{} und somit können wir
\mavergleichskette
{\vergleichskette
{ p^s(u-v^2)
}
{ = }{cp^r
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
schreiben. Kürzen in $\Z$ ergibt
\mavergleichskette
{\vergleichskette
{ u-v^2
}
{ = }{cp^{r-s}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
also
\mathl{u=v^2 \mod p}{.} Also ist $u$ ein quadratischer Rest modulo $p$ und nach dem ersten Teil auch modulo $p^r$.
Die Umkehrung von (2) ist nach der unter (1) bewiesenen Aussage klar.
\inputfaktbeweis
{Restklassenringe (Z)/Quadratreste/Gerade Primzahlpotenz/Reduktion/Fakt}
{Satz}
{}
{
Es sei
\mathl{p=2}{} und sei
\mathl{k \in \Z/(2^r)}{.}
\aufzaehlungzwei {Für
\mathl{r=2}{} ist $k$ genau dann quadratischer Rest, wenn
\mathl{k=0,1 \mod 4}{} ist.
} {Für
\mathl{r \geq 3}{} und $k$ ungerade ist $k$ genau dann quadratischer Rest modulo $2^r$, wenn
\mathl{k= 1 \mod 8}{} ist.}
}
{
(1) ist trivial.
(2). In
\mathl{\Z/(8)}{} ist von den ungeraden Zahlen lediglich die $1$ ein Quadrat, sodass der Ringhomomorphismus
\maabbdisp {} { \Z/(2^r) } { \Z/(8)
} {}
für
\mathl{r \geq 3}{} zeigt, dass die numerische Bedingung notwendig ist. Es sei diese umgekehrt nun erfüllt, also
\mathl{a \in (\Z/(2^r))^\times}{} mit
\mathl{a=1 \mod 8}{.} Dann kann man nach
Bemerkung 5.12
\mavergleichskettedisp
{\vergleichskette
{a
}
{ =} { \pm 5^{i}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
schreiben. Dies gilt aber auch modulo $8$, woraus sofort folgt, dass $i$ gerade und dass das Vorzeichen positiv ist. Dann ist
\mathl{5^{i/2}}{} eine Quadratwurzel von $a$ in
\mathl{\Z/(2^r)}{.}
Wir werden uns im folgenden weitgehend darauf beschränken, welche Zahlen modulo einer Primzahl Quadratreste sind. Da allerdings die Primfaktorzerlegung einer größeren Zahl nicht völlig unproblematisch ist, müssen wir später auch Techniken entwickeln, die ohne Kenntnis der Primfaktorzerlegung auskommen. Direkt beantworten lässt sich die Frage, wann $-1$ ein Quadratrest modulo einer Primzahl ist.
\inputfaktbeweis
{Restklassenringe (Z)/Quadratreste/-1/Fakt}
{Satz}
{}
{
Es sei $p$ eine \definitionsverweis {Primzahl}{}{.} Dann gelten folgende Aussagen.
Für
\mathl{p =2}{} ist
\mathl{-1=1}{} ein Quadrat in
\mathl{\Z/(2)}{.}
Für
\mathl{p =1 \! \! \! \! \mod 4}{} ist $-1$ ein Quadrat in
\mathl{\Z/(p)}{.}
Für
\mathl{p = 3 \! \! \! \! \mod 4}{} ist $-1$ kein Quadrat in
\mathl{\Z/(p)}{.}
}
{
Die erste Aussage ist klar, sei also $p$ ungerade. Nach
Satz 5.3
ist die Einheitengruppe zyklisch der geraden Ordnung
\mathl{p-1}{.} Identifiziert man
\mathl{( { \left( \Z/(p) \right) }^{\times} , 1, \cdot)}{} mit
\mathl{(\Z/(p-1),0, +)}{,} so entspricht
\mathl{-1}{} dem Element
\mathl{{ \frac{ p-1 }{ 2 } }}{,} und $-1$ besitzt genau dann eine Quadratwurzel, wenn
\mathl{{ \frac{ p-1 }{ 2 } }}{} in
\mathl{\Z/(p-1)}{} ein Vielfaches von $2$ ist. Dies ist aber genau dann der Fall, wenn
\mathl{{ \frac{ p-1 }{ 2 } }}{} selbst gerade ist, was zu
\mathl{p =1 \mod 4}{} äquivalent ist.
| << | Kurs:Zahlentheorie (Osnabrück 2016-2017) | >> |
|---|