eine Primitivwurzel modulo berechnen

Question

Aufgabe:

Gesucht ist eine Primitivwurzel modulo 41

Problem/Ansatz:

Ich tue mir noch etwas schwer, wenn wir eine Primitvwurzel finden müssen, da wir mit "ausprobieren und testen" abgespeist wurden... In der Klausur könnte es jedoch mit einfach ausprobieren zeitliche Probleme geben...

ich weiß, dass a eine PW mod41 ist ⇔ ord₄₁(a)=Φ(41)=40. Zudem muss gelten dass der ggt(a,41)=1

Bei mein Vorgehen bin ich bisher immer so vorgegangen, indem ich überprüft habe ob a^{\( \frac{Φ(41}{p} \)} ≠1 (mod41), wenn p meine Primteiler von Φ(41)

Wenn ich nun jedoch 2,3,5 zum "ausprobieren" wähle komme ich immer darauf, dass diese keine PW sein können..

Habe ich hier einen falschen Ansatz gewählt oder gibt es einen "Trick" wie man schneller sieht, welche zahl ich testen muss?

Answer 1

Probiere mal die 6 für 41 , 109, 159,
die 7 für 71 und die 19 für 191,

, das habe ich beim googeln unter den Stichworten: Primitivwurzel Uni Bielefeld gefunden.