How to find primitive roots of big numbers modulo n, like 121? I know how to find primitive roots of prime numbers and small numbers as 14, where phi(14) = 6. At small numbers i just look at each element and determine the order. If the order is the same as $\phi(n)$ i have a primitive root, this is a lot of work but it seemed to work out if there is an easier method i would love to hear it :).
The problem is that when i look at a number such as $121$ i have $\phi(121) = 110$. I can't go through all elements, because that would cost me to much time. Are there neat tricks to solve this one.
I know $121 = 11 \cdot 11$ and i know the primitive roots of mod 11, if one can determine the primitive roots of $p^2$ by knowing the roots of $p$ i would like to know how that is possible (it's just an hypothesis, maybe this isn't true at all)
Any hints would be very welcome!
Kees

In general, if $g$ is a primitive root mod $p$ then $g$ or $g+p$ is a primitive root mod $p^2$.
For $p=11$, we have that $g=2$ works.
It is enough to test that $2^{110/q}\not \equiv 1 \bmod 121$ for $q=2,5,11$, the prime divisors of $110=\phi(121)$.
