Bestimmen Sie eine Primitivwurzel modulo 9^k für alle k ∈ ℕ

Question

Aufgabe:

Bestimmen Sie eine Primitivwurzel modulo 9^k für alle k ∈ ℕ

Problem/Ansatz:

Wir haben das bisher nur gemacht, wenn der Modul eine Primzahl war. Dann sind wir folgendermaßen vorgegangen:

Wir haben erstmal eine Primitivwurzel g mod p bestimmt. Eine Primitivwurzel, die die Aufgabe löst wäre dann gegeben durch n=g+x·p

Dann habe ich folgende 2 "Forneln" über die ich dann das x bestimmen kann:

g^p-1=1+p·y , um das y für die Kongruenz (p-1)·g^p-2 ·x≡-y mod p zu bestimmen. Das x, das bei der Kongruenz herauskommt ist das, welches bei n=g+x·p nicht für x einsetzen darf. Setzt man einen anderen beliebigen Wert ein, so bekommt man für n eine Primitivwurzel die für ein beliebiges p^k Primitivwurzel wäre.

Jetzt ist es in der Aufgabe mit 9^k ja keine Primitivwurzel. Wie muss ich das Vorgehen dann anpassen? 9 hat ja als einzigen Primfaktor die 3. Könnte ich z.B. statt der 9 das Ganze für 3 bestimmen und dann das Vorgehen so belassen? Oder muss ich die Formeln anpassen? Wenn ja, wie?

Answer 1

Die "Anpassung" ist ganz einfach. Wenn etwas eine Primitivwurzel

mod \(3^k\) für alle nat. \(k\geq 2\) ist, dann insbesondere

für alle geraden \(k=2m\), also mod \(3^k=9^m\) mit \(m\geq 1\).

Z.B. erhält man so 2 als Primitivwurzel mod \(9^m\).