I am asked to find the primitive roots of unity mod 23, and recommended to use Fermat's Little Theorem to help simplify calculation. I know that, once I've found one, I can find all others by finding all $gcd(p-1,k)$ where $p=23$ and $k$ is an exponent of the root. But I don't see the use of Fermat's Little Theorem except in proving the existence of roots. I'm guessing the suggestion is meant to facilitate finding one root.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Well...it helps in that you know in advance that the order of a given element must be a divisor of $22$, thus the order must be $1,2,11$ or $22$. You know the elements of order $1,2$ so you just have to rule out $11$. $\endgroup$– luluApr 15, 2019 at 11:27
-
$\begingroup$ In general, no efficient method to find a primitive root is known. $\endgroup$– PeterApr 15, 2019 at 14:12
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It helps in that you know in advance that the order of a given element must be a divisor of $22$, thus the order must be $1,2,11$ or $22$. You know the elements of order $1,2$ so you just have to rule out $11$.
To be specific: we check that $2^{11}\equiv 3^{11}\equiv 1 \pmod {23}$ so neither are primitive roots. However $5^{11}\equiv -1 \pmod {23}$ so $5$ is a primitive root.
