Originally Posted by
ThePerfectHacker The direct way with to deal with $\displaystyle 11$ is to list all $\displaystyle n$ with $\displaystyle \gcd (n,11)=1$ so $\displaystyle n=1,2,...,10$. And now eliminate each of these numbers. For example, take $\displaystyle n=4$. Check whether the order of $\displaystyle 4$ mod $\displaystyle 11$ is $\displaystyle \phi(11) = 10$. Remember order means the smallest exponent $\displaystyle k$ so that $\displaystyle 4^k\equiv 1(\bmod 11)$. But since $\displaystyle 4^{10}\equiv 1(\bmod p)$ (Fermat's theorem) it follows by properties of orders that $\displaystyle k|10$ so $\displaystyle k=1,2,5,10$. Since it cannot be $\displaystyle 1$ it means you just need to check $\displaystyle k=2,5,10$. A simple calculation will show that $\displaystyle k=5$ is the order, so $\displaystyle 4$ is not a primitive root. So that eliminates one number on the list $\displaystyle \{ 1,2,...,10\}$. Now pick another number, say $\displaystyle 2$, using the approach as above you will find that $\displaystyle k=10$. So that means $\displaystyle 2$ is a primitive root mod $\displaystyle 11$. Now you can save yourself a lot of time, since you found one primitive root all other primitive roots are $\displaystyle 2^{m}$ where $\displaystyle 1\leq 1\leq 10$ and $\displaystyle \gcd(m,\phi(11)) = \gcd(m,10)=1$. In this case $\displaystyle m=1,3,7,9$. Thus, $\displaystyle 2, 2^3 \equiv 8, 2^7\equiv 7, 2^9\equiv 6$ are the primitive roots.