Die wöchentlichen Übungsaufgaben können jeweils Donnerstag abends von dieser Seite heruntergeladen werden, und die Lösungen können (soweit nicht anders angegeben) jeweils in der darauf folgenden Woche Mittwochs oder freitags zu Beginn der Übungen zur Korrektur abgegeben werden.

Übungsblätter

1 2 3 4 5 6 7 8 9 10 11 12
\(\newcommand {\mat}[4] {\left(\begin{smallmatrix}{#1}&{#2}\\{#3}&{#4}\end{smallmatrix}\right)}\) \(\newcommand {\C} {{\mathbb C}}\) \(\newcommand {\E} {{\mathbb E}}\) \(\newcommand {\F} {{\mathbb F}}\) \(\newcommand {\Pro} {{\mathbb P}}\) \(\newcommand {\Q} {{\mathbb Q}}\) \(\newcommand {\R} {{\mathbb R}}\) \(\newcommand {\Z} {{\mathbb Z}}\) \(\newcommand {\P}[1] {{\mathbb P}^{#1}}\) \(\newcommand {\sym}[1] {{\operatorname{#1}}}\) \(\newcommand {\SL}[1] {{\sym{SL}(2,#1)}}\) \(\newcommand {\hil}[3] {\left({#2},{#3}\right)_{#1}}\) \(\newcommand {\leg}[2] {\left(\tfrac{#1}{#2}\right)}\)

Übungsaufgaben zur Elementaren Zahlentheorie 2016 - Blatt 4

Abgabetermin: Do 12. Mai 2016 nach der Vorlesung.

Sei \(w\) eine Primitivwurzel modulo \(p^2\), wobei \(p\) eine ungerade Primzahl ist. In der Vorlesung wurde gezeigt: für jedes \(\alpha\ge 1\) existiert eine zu \(p\) teilerfremde Zahl \(n_\alpha\), sodass \[ w^{\varphi(p^{\alpha-1})} = 1 + n_\alpha p^{\alpha-1} \] gilt.

Zeigen Sie, dass hieraus folgt, dass \(w\) eine Primitivwurzel modulo jeder Potenz \(p^\alpha\) ist.

Erklären Sie, an welcher Stelle im Beweis des Satzes, dass zu jeder ungeraden Primzahlpotenz \(p^\alpha\) eine Primitivwurzel existiert, benötigt wurde, dass \(p\) ungerade ist.

Sei \(\alpha\ge 3\). Zeigen Sie: zu jeder ungeraden Zahl \(a\) gibt es genau ein \(0\le t \lt 2^{\alpha-2}\) und genau ein \(\varepsilon \in\{\pm 1\}\), sodass \[ a \equiv \varepsilon 5^t \bmod 2^\alpha . \]

Finden Sie in Termen der Primfaktorzerlegung eine hinreichende und notwendige Bedingung dafür, dass eine gegebene Zahl \(m\) die Eigenschaft hat, dass \[ a^{m-1}\equiv 1 \bmod m \] für alle zu \(m\) teilerfremden \(a\) gilt.

Finden Sie die ersten zusammen gesetzten Zahlen \(m\), die vorstehende Kongruenz für alle zu \(m\) teilerfremden \(a\) erfüllen.

Bestimmen Sie empirisch den Prozentsatz der Primzahlen, für die \(2\) eine Primitivwurzel ist. (Hinweis: Implementieren Sie in Ihrem CAS eine Funktion ps( N), die zu gegebenem \(N\) den Prozentsatz aller Primzahlen unterhalb \(N\) bestimmt, für die \(2\) eine Primitivwurzel modulo \(p\) ist. Bestimmen Sie dann exprimentell den Grenzwert \(\lim_N ps(N)\).)