confusion on how to find primitive roots (find primitive root mod 23, 46, 529, 12167)
Matthew Harrington 
We were asked to find primitive root mod $23$, $46$, $529$, $12167$.
My lecturer gave us a hint in finding primitive root mod $23$, but I am confused about his reasoning. My lecturer said $a$ would be a primitive root if $a^2 \not\equiv 1 \bmod 23$ and $a^{11} \not\equiv 1 \bmod 23$ as $\phi(23) = 22$ because the order of a number mod $23$ can only be $2$, $11$, or $22$. Why must $a^2$ and $a^{11}$ not be congruent to $1$ mod $23$, and why is that the order of a number mod $23$ can only be $2$, $11$, or $22$?
I checked $a=2, a=3, a=5$, and found $a=5$ satisfies the condition thus is a primitive root. From this, I found the primitive root mod $529$ using the fact that $23^2=529$ thus $5$ or $5+23$ must be a primitive root. I found $5^{506} \equiv 1 \bmod 529$ using a calculator. (is there a faster way to do this?)
I also can't see any trick in finding primitive root $46$ and $12167$, also I have noted $2 \times 23$ and $12167 = 529 \times 23$.
$\endgroup$ 7 Reset to default
