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 zu Beginn der Donnerstag-Vorlesung zur Korrektur abgegeben werden.

Übungsblätter

1 2 3 4 5 6 7 8 9 10 11
\(\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 2018 - Blatt 3

Abgabetermin: Do 03. Mai 2018 zu Beginn der Übung.

Ich möchte die Äpfel meiner letzten Ernte verschenken. Wenn ich sie auf 51 Leute so verteile, dass jeder die gleiche Anzahl und möglichst viel erhält, behalte ich 13 übrig. Verteile ich sie aber auf 49 Leute, jedem gleich viele und möglichst viele, so behalte ich 16 übrig. Wie viel Äpfel habe ich mindestens?

Bestimmen Sie alle Nullstellen modulo \(m\) des Polynoms \(f\) für

  1. \(f(x)=x^2 + 2\,x + 48\) und \(m=71\),
  2. \(f(x)=x^2+215\,x+1184\) und \(m=5183\),
  3. \(f(x)=x^2-1\) und \(m=1024\).

Bestimmen Sie experimentell den Prozentsatz aller Primzahlen \(p\), sodass \(2\) (bzw. \(3\), \(5\)) Primitivwurzeln modulo \(p\) sind.

Sei \(p\) eine ungerade Primzahl.

(i) Bestimmen Sie eine "gute" untere Schranke für die Wahrscheinlichkeit, dass eine gegebene Zahl \(a\) eine Primitivwurzel modulo \(p\) ist.

(ii) Beschreiben Sie einen Test, der in \(O(\log p)\) Schritten entscheidet, ob eine gegebene Zahl \(a\) eine Primitivwurzel modulo \(p\) ist.

Implementieren Sie in Ihr CAS ein Funktion pw_dist( p), die zu einer gegebenen Primzahl \(p\) die Verteilung der Primitivwurzeln modulo \(p\) im Intervall \([1,p-1]\) veranschaulicht. (Hinweis: In Sage kann man den decorator @interact benutzen - googlen Sie ...)