How would one go about proving/disproving whether $g$, a multiplicative generator mod $p$, is also a multiplicative generator mod $p^2$?


I assume $p$ is an odd prime.

It suffices to check if $g^{p-1}$ is $1$ mod $p^2$ or not. If it is, then it is not a generator. (Clear as its order is $p-1$ and not the needed $(p-1)p$.)

If it is something else, then it is. This is because its order mod $p^2$ must be a multiple of the order mod $p$, which is $p-1$ and a divisor of $p(p-1)$. So if it is greater than $(p-1)$, it can only be $p(p-1)$.

Both cases can happen. One can show though that at least on of $g$ and $g+p$ will be a generator mod $p^2$.

  • $\begingroup$ it looks close to the lifting in Hensel lemma ? $\endgroup$ – reuns Nov 1 '16 at 22:10
  • $\begingroup$ Yes, it's closely related to this. $\endgroup$ – quid Nov 1 '16 at 22:24

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.