Wurzelziehen und Übungen

Eine kurze Übersicht über das Wurzelziehen modulo \(m\). Allgemeine quadratische Kongruenzen kann man dann natürlich mithilfe der \(p\)-\(q\)-Formel lösen. Für das Wurzelziehen modulo \(p\) mit einer Primzahl \(p\equiv 1\bmod 4\) kann man den Tonelli-Shanks-Algorithmus verwenden, aber den werdet ihr im Rahmen der Vorlesung „Elementare Zahlentheorie“ sicher nicht brauchen.

Bei den Tests aus dem SoSe 2008 könnt ihr euch ansehen, wie Klausuraufgaben in der Zahlentheorie aussehen könnten.

Aufgaben

  1. Bestimme die Lösungsmenge von \(x\equiv 1 \bmod 9,\quad x\equiv 8\bmod 21,\quad x\equiv 4\bmod 7\).
  2. Bestimme eine Lösung von \(x^2+2x-4\equiv 0\bmod 55\).
  3. Löse \(x^2\equiv 22\bmod 27\).
  4. Finde alle Primitivwurzeln modulo \(17\). Berechne dazu geeignete Potenzen um zu überprüfen, ob ein Element Ordnung \(φ(17)\) hat. Ist eine Primitivwurzel \(g\) gefunden, kann man die restlichen leicht hinschreiben. (Für welche \(x\) ist \(g^x\) wieder eine Primitivwurzel?)

Beweise

Blatt 4, Aufgabe 1

Sei \(p\ne 2\) eine Primzahl und \(w\) eine Primitivwurzel modulo \(p^2\), also \(\mathrm{ord}_{p^2} w=φ(p^2)=p(p-1)\). Zudem gebe es für jedes \(α\ge 1\) eine zu \(p\) teilerfremde Zahl \(n_α\), so dass \[ w^{φ(p^{α-1})} = 1+n_α p^{α-1} \] gilt.

Der Induktionsanfang ist also bereits erledigt. Nehmen wir nun an, dass \(w\) eine Primitivwurzel modulo \(p^{α-1}\) ist, also \(\mathrm{ord}_{p^{α-1}} w=φ(p^{α-1})=p^{α-2}(p-1)\). Das bedeutet, dass \(w^{p^{α-2}(p-1)}\equiv 1\bmod p^{α-1}\) (das gilt nach Euler immer) und \(w^{p^{α-2}(p-1)/q}\not \equiv 1\bmod p^{α-1}\) ist für alle echten Teiler \(q\) von \(p^{α-2}(p-1)\).

Wir müssen nun zeigen, dass \(n:=\mathrm{ord}_{p^α}(w)\ge φ(p^α)\) ist, dass also \(w^n\not \equiv 1\bmod p^α\) falls \(n=\frac{φ(p^α)}q\) und \(q\) ein echter Teiler von \(φ(p^α)=p^{α-1}(p-1)\) ist. Da aus \(w^n\equiv 1\bmod p\) folgt, dass \(p-1\) ein Teiler von \(n\) ist (warum?), genügt es schon zu zeigen, dass \[ w^{p^{α-1}(p-1)/p}=w^{p^{α-2}(p-1)} \not \equiv 1\bmod p^α \] gilt. Das folgt aber sofort aus der Existenz von \(n_α\), denn \(1+n_αp^{α-1} \not \equiv 1\bmod p^α\), da \(n_α\) teilerfremd zu \(p\) ist.

Aufgabe 2

Im Beweis der Existenz von \(n_α\) wird benutzt, dass \(p\mid {p \choose 2}\) ist, was aber für \(p=2\) falsch ist, denn \({2\choose 2} = 1\).