If I find $a$ is PR mod p, then a theorem states that either $a$ itself or $a+p$ is the PR mod $p^2$. Is there a fast approach to check the exponents of $a$, instead of going through every element in $\{1,...,\phi(p^2)\}$? I recall that the exponent of $a$ ($ord_{p^2}(a)$) takes value in the set all the divisors of $\phi(p^2)$, but I am not sure if I remember it correctly.

More over since modulo $p^2$ extends from modulo $p$, I wonder if $\phi(p)$ is going to involve in the exponent $e$ of $a^e \equiv 1$ mod $p^2$? Thanks in advance!

A concrete example: 2 is found to be a primitive root modulo 13, how can I show 2 is also a root mod $13^2$? For exponent of 2, am I going to check all the divisors of $\phi(13^2)$= 156: $\{1, 2, 3, 4, 6, 12, 13, 26, 39, 52, 78, 156\}$, and show 156 itself is the least $e$ such that $2^e\equiv 1$ mod $13^2$?

A relevant, and more general result: enter image description here (https://en.wikipedia.org/wiki/Primitive_root_modulo_n)


1 Answer 1


Suppose that $a$ is a primitive root (mod $p$). A more precise result is:

  • $a$ is a primitive root (mod $p^2$) if and only if $a^{p-1}\not\equiv1$ (mod $p^2$);
  • of the $p$ numbers $a$, $a+p$, ..., $a+(p-1)p$, exactly one of them satisfies $(a+kp)^{p-1}\equiv 1$ (mod $p^2$).

So you can simply compute $a^{p-1}$ modulo $p^2$ to determine the answer.

  • $\begingroup$ Is there anywhere I can find the proof for this result? The course I am taking has omitted it but the result is a useful one $\endgroup$
    – siegfried
    Oct 14, 2020 at 5:10
  • $\begingroup$ Niven/Zuckerman/Montgomery will have it, for example. $\endgroup$ Oct 14, 2020 at 6:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .