0
$\begingroup$

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.

$\endgroup$
  • 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$ – lulu Apr 15 at 11:27
  • $\begingroup$ In general, no efficient method to find a primitive root is known. $\endgroup$ – Peter Apr 15 at 14:12
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.