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 5

Abgabetermin: Do 19. Mai 2016 nach der Vorlesung.

Entwickeln Sie einen möglichst optimalen Algorithmus power(a,n) zur Berechnung von \(a^n\), und berechnen Sie die Anzahl der Rechenschritte in Abhängigkeit von \(n\).

Bestimmen Sie eine Lösung von \[ x^2\equiv 2 \bmod 7^{100} . \]

Finden Sie für die \(3\) Primzahlen \(p\) mit \(10^6 \lt p \lt 10^6+100\), die kongruent \(1\) modulo \(4\) sind, eine Darstellung als Summe zweier perfekter Quadrate.

Sei \(p\) eine Primzahl. Die Dirichletcharaktere modulo \(p\) bilden eine Gruppe (bezüglich argumentweiser Multiplikation). Bestimmen Sie die Ordnung dieser Gruppe.

Sei \(p\) eine Primzahl und \(l\) eine positive ganze Zahl. Zeigen Sie:

  1. Ist \(l\) teilerfremd zu \(p-1\), so ist die Kongruenz \(a\equiv x^l\bmod p\) für jedes \(a\) lösbar.
  2. Ist \(l\) Teiler von \(p-1\), so gilt für jedes zu \(p\) teilerfremde \(a\) \[ \sum_{\chi^l=1} \chi(a) = \begin{cases} \varphi(l)&\text{falls }a\equiv x^l\bmod p\text{ lösbar ist,}\\ 0&\text{sonst.} \end{cases} \]
Hierbei ist die Sume über alle Dirichletcharakter modulo \(p\) zu nehmen, für die \(\chi^l=1\) gilt.

Können Sie eine geschlossene Formel für \(\sum_{\chi^l=1} \chi(a)\) mit beliebigem \(l\) angeben?