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$.

  • $\begingroup$ 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$? $\endgroup$ – abuchay Mar 3 '18 at 15:23
  • $\begingroup$ @abuchay, yes, the same statement holds for $p^k$. $\endgroup$ – lhf Mar 3 '18 at 15:34
  • 1
    $\begingroup$ Thanks. Also after searching through internet, I found some other generalization here: people.math.gatech.edu/~mbaker/pdf/primroots.pdf $\endgroup$ – abuchay Mar 3 '18 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.