# Find a primitive root of (a) $U(\mathbb{Z}/121\mathbb{Z})$, and (b) $U(\mathbb{Z}/18\mathbb{Z})$

Find a primitive root of (a) $U(\mathbb{Z}/121\mathbb{Z})$ and (b) $U(\mathbb{Z}/18\mathbb{Z})$.

Both of them are cyclic groups so primitive roots exist for both of them, but I don't know their generators. I know that $U(\mathbb{Z}/18\mathbb{Z}) \cong U(\mathbb{Z}/2\mathbb{Z})\times U(\mathbb{Z}/3^2\mathbb{Z})$. Also $\phi(18) = \phi(3^2) \phi(2) = 6$ and $\phi(121) = \phi(11^2) = 110$. So I need to find $a^{110} \equiv 1 \mod121$ and $b^{6} \equiv 1 \mod18$. I guess it will be easier to find $b$ by checking through units modular 18 but how do I find $a$?

Hint: If $p$ is prime and $g$ is a primitive root mod $p$, then $g$ or $g+p$ is a primitive root mod $p^2$.
• If $p$ is prime and $g$ is a primitive root mod p, then $g$ or $g+p$ is a primitve root mod $p^2$. So is there a generalization for primitive root of $p^k$? – abuchay Mar 3 '18 at 15:23
• @abuchay, yes, the same statement holds for $p^k$. – lhf Mar 3 '18 at 15:34