# How does Fermat's Little Theorem help find primitive roots of unity?

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.

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

## 1 Answer

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.