Suche

Elementare Zahlentheorie


Übungsblatt als .pdf $ \newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\lgd}[2]{\left(\frac{#1}{#2}\right)} \newcommand{\F}{\mathbb{F}} \newcommand{\C}{\mathbb{C}} \newcommand{\N}{\mathbb{N}} \newcommand{\coloneqq}{:=} \newcommand{\eqqcolon}{=:} \newcommand{\legendre}[2]{\left(\frac{#1}{#2}\right)} \newcommand{\zmatrix}[4]{\left(\begin{matrix}#1\\ #3\end{matrix}\right)} \DeclareMathOperator{\gal}{Gal} \DeclareMathOperator{\mat}{Mat} \DeclareMathOperator{\ggt}{ggT} \DeclareMathOperator{\kgv}{kgV} \DeclareMathOperator{\id}{Id} \DeclareMathOperator{\modu}{mod} \DeclareMathOperator{\aut}{Aut} \DeclareMathOperator{\sym}{S} \DeclareMathOperator{\asym}{A} \DeclareMathOperator{\gl}{GL} \DeclareMathOperator{\discr}{disc} \DeclareMathOperator{\zerf}{Zerf} \DeclareMathOperator{\er}{ER} \DeclareMathOperator{\cha}{char} \DeclareMathOperator{\ord}{ord} \DeclareMathOperator{\syl}{Syl} \DeclareMathOperator{\slg}{SL} \DeclareMathOperator{\gal}{Gal} \DeclareMathOperator{\mat}{Mat} \DeclareMathOperator{\ggt}{ggT} \DeclareMathOperator{\kgv}{kgV} \DeclareMathOperator{\id}{Id} \DeclareMathOperator{\modu}{mod} \DeclareMathOperator{\aut}{Aut} \DeclareMathOperator{\sym}{S} \DeclareMathOperator{\asym}{A} \DeclareMathOperator{\gl}{GL} \DeclareMathOperator{\discr}{disc} \DeclareMathOperator{\zerf}{Zerf} \DeclareMathOperator{\er}{ER} \DeclareMathOperator{\cha}{char} \DeclareMathOperator{\ord}{ord} \DeclareMathOperator{\syl}{Syl} \DeclareMathOperator{\im}{Im} $

Mögliche Literatur: Einführung in die Zahlentheorie von P. Müller (die entsprechenden Abschnitte aus den Kapiteln 5 und 9).

Aufgabe 1 (Satz von Wilson)

Beweise die folgende Version des Satzes von Wilson: Ist $ n\in\N $ (ohne Einschränkung $ n>1 $ ), dann gilt $$ (n-1)!\equiv -1\mod n\quad\Leftrightarrow\quad n\text{ ist eine Primzahl.} $$

Tipps

Zu " $ \Leftarrow $ '' (dem "ursprünglichen'' Satz von Wilson): Versuche, die Elemente von $ \Z_n^\times $ in passende Paare zu sortieren, ein naheliegender Gedanke wäre beispielsweise, Paare der Form $ (r,r^{-1}) $ zu bilden - dabei ist allerdings der Fall selbstinverser Elemente zu berücksichtigen, also solcher $ r\in\Z/n\Z $ mit $ r=r^{-1} $ . Zeige, dass aber für eine Primzahl $ n $ die einzigen selbstinversen Elemente in $ \Z/n\Z $ die beiden offensichtlichen Kandidaten $ 1 $ und $ n-1\equiv -1\mod n $ sind.

Aufgabe 2

Zeige, dass für alle $ n\in\N $ gilt $$ \sum_{d\vert n}\phi(d)=n, $$ wobei $ \phi $ die Eulersche Phi-Funktion bezeichnen soll.

Tipps

Eine elementare Möglichkeit: Betrachte die Menge der Brüche $ i/n $ , für $ 1\leq i\leq n $ , wobei Du jeden Bruch vollständig kürzt und die Menge anschließend nach den auftretenden Nennern unterteilst.
Etwas elegantere Variante: Betrachte eine zyklische Gruppe $ G $ der Ordnung $ n $ - was weißt du über die Teiler von $ n $ und die Untergruppen von $ G $ ? Überlege dir, dass es zu jedem $ d\vert n $ gerade $ \phi(d) $ Elemente der Ordnung $ d $ in $ G $ gibt.

Bemerkung (Erinnerung an das Legendre Symbol)

Für eine Primzahl $ p\neq 2 $ heißt ein $ a\in\Z $ quadratischer Rest modulo $ p $ , falls es ein $ b\in\Z $ gibt mit $ b^2\equiv a\mod p $ , in anderen Worten, falls die Gleichung $ X^2-a=0 $ modulo $ p $ lösbar ist. Man definiert das Legendre-Symbol $$ \lgd{a}{p}\coloneqq \left\{\begin{array}{rl} +1&\text{ falls }a\text{ quadratischer Rest mod }p \\ 0&\text{ falls }p\vert a \\ -1&\text{ sonst }\end{array}\right. $$ Der beträchtliche Nutzen des Legendre-Symboles ergibt sich aus den folgenden Identitäten, die es ermöglichen, das Legendresymbol für ein beliebiges Paar aus einer Primzahl $ p $ und einem $ a\in\Z $ effizient zu berechnen (wie immer keine Gewähr auf Vollständigkeit der nachfolgenden Liste von das Legendre-Symbol betreffenden Identitäten)

  • Ist $ a\equiv b\mod p $ , so ist $ \lgd a p =\lgd b p $ .
  • Für $ a,b\in\Z $ ist $ \lgd{ab}{p}=\lgd a p\cdot\lgd b p $ .
  • Für Primzahlen $ p,q\neq 2 $ ist $ \lgd p q=\left\{\begin{array}{rl} -\lgd q p&\text{falls }p\equiv 3\mod 4\quad\wedge\quad q\equiv 3\mod 4\\ \lgd q p&\text{sonst}\end{array}\right. $
  • Es ist $ \lgd{-1}{p}=(-1)^{\frac{p-1}{2}} $ .
  • Es ist $ \lgd 2 p=(-1)^{\frac{p^2-1}{8}} $ .

Aufgabe 3 (Rechnen mit dem Legendre - Symbol)

Ist $ 12345 $ ein quadratischer Rest modulo $ 331 $ (Zahlenbeispiel von Wikipedia)?

Tipps

$ 12345=3\cdot 5\cdot 823 $ .

Aufgabe 4

Sei $ p $ eine Primzahl. Zeige, dass es in $ \Z_p\setminus \{0\} $ genauso viele quadratische Reste wie quadratische Nicht-Reste gibt (Nämlich wie viele?).

Tipps

Betrachte die Menge $ \{a^2~:~a\in\Z_p\setminus\{0\}\} $ . Was bedeutet $ a^2=b^2 $ für $ a $ und $ b $ ? Tipp: $ a^2-b^2=(a-b)(a+b) $ .
Alternative 1: Wähle einen Erzeuger $ a $ von $ \Z_p^\times $ (wieso gibt es einen solchen?) und zeige, dass ein beliebiges $ b\in\Z_p^\times $ , welches sich ja eindeutig als $ b=a^j $ für ein $ 0\leq j\leq p-1 $ schreiben lässt, genau dann ein Quadrat ist, wenn $ j $ gerade ist.
Alternative 2 (Umformulierung der ursprünglichen Variante): Überlege Dir, dass Quadrieren, also die Abbildung $$ (\bullet)^2\colon\Z_p^\times\rightarrow\Z_p^\times,\quad x\mapsto x^2, $$ ein Gruppenhomomorphismus ist, dessen Bild nach Konstruktion gerade die Quadrate in $ \Z_p^\times $ sind. Bestimme dann dessen Kern und verwende den Homomorphiesatz.

Aufgabe 5

Beweise das Euler-Kriterium: Für eine Primzahl $ p\neq 2 $ und ein $ a\in \Z $ gilt $$ \lgd a p\equiv a^{\frac{p-1}{2}}\mod p. $$

Tipps

Das Polynom $ X^{\frac{p-1}{2}}-1 $ hat über dem Körper $ \Z_p $ gerade $ (p-1)/2 $ Nullstellen. Wieso sind quadratische Reste modulo $ p $ sicher Nullstellen dieses Polynomes (in $ \Z_p $ )?