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
 A: 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)$.
A: Like Order of numbers modulo $p^2$
For prime $p,$
if ord$_pa=d,$
either ord$_{p^2}a=pd$ or  ord$_{p^2}(a+kd)=pd$  if $(k,p)=1$
If $d=\phi(p)=p-1,a$ is primitive root of $p$
and $p=11$
A: Assume that $p>2$. In order to find a generator for $G=\left(\mathbb{Z}/_{p^k\mathbb{Z}}\right)^*$, we may apply the following algorithm:
Step 0: Find a generator of $\mathbb{F}_p^*$ by testing $2,3,4,\ldots$. Assuming the GRH, that step requires at most $C\log^2 p$ tests;
Step 1: Apply Hensel's lifting lemma to lift a generator for $\left(\mathbb{Z}/_{p^m\mathbb{Z}}\right)^*$ to a generator for $\left(\mathbb{Z}/_{p^{m+1}\mathbb{Z}}\right)^*$ through translations.
A: We have $\phi(121) = 110$.
Moreover, using the 'arithmetic pattern chasing' indicated in
At least one well-defined cyclic subgroup of $(\mathbb{Z}/{p^2}\mathbb{Z})^\times$, for prime $p$
and
Prove that for prime $p \gt 2$, $(p - 1)^{p - 1} \equiv p+1 \pmod{p^2}$.
all the residue numbers in $\left(\mathbb{Z}/_{121\mathbb{Z}}\right)^{\times}$ of order $22 = 2 \times 11$ can be immediately listed out without using a calculator; there are $10$ numbers (as expected since $\phi(22) = 10$):
Starting at $g = 10 = 11 - 1$ keep adding $2 \times 11$ while less than $120 = 121 -1$:
$\quad 10, 32, 54, 76, 98$
Now add $11$ to each number in the above (partial) list to complete the work,
$\quad 21, 43, 65, 87, 109$
Since $\frac{110}{22} = 5$, all that remains is to find an $x \in \left(\mathbb{Z}/_{121\mathbb{Z}}\right)^{\times}$ such that the residue of $x^5$ is on our list of $10$ numbers.
Observing that $2^5 = 32$ we've found that $[2] \in \left(\mathbb{Z}/_{121\mathbb{Z}}\right)^{\times}$ is a primitive root of unity.
Also see this for the relevant details.
