# Primitives roots of $p$ and $p^2$.

It is well known that for any primitive root $g$ of a prime $p$, either $g$ or $g + p$ is a primitive root of $p^2$

Do there exist any primes for which $g$ is a primitive root of $p^2$ for all primitive roots $g$ of $p$. Does the reverse exist (i.e. $g$ is not a primitive root of $p^2$ for all $g$)? Are there any general conditions for this to be true?

Edit: As Quimey points out, 3 and 2 satisfy the conditions respectively. Are there any other non-trivial examples?

-
3 for the first property and 2 for the second, am I right? –  Quimey Apr 9 '12 at 13:54
@Quimey yes, that does seem to be true. I've added to the question asking for some general conditions for this to be true. Do you know of any less trivial examples? –  EuYu Apr 9 '12 at 13:57

There is a slight problem with the questions, in that if $g$ is a primitive root of $p$, then $g+kp$ should really be considered as being "the same" primitive root of $p$ as $g$. For $p$ an odd prime, there are exactly $(p-1)\varphi(p-1)$ primitive roots of $p^2$, and $\varphi(p-1)$ primitive roots of $p$. For any primitive root $g$ of $p$, exactly one of the numbers $g+kp$, where $0 \le k \le p-1$, is not a primitive root of $p^2$.

Thus the answer to your question is completely dependent on which numbers we pick as our complete set of representatives of the primitive roots of $p$. So to attack the question, we need to put constraints on this set of representatives. A reasonable constraint that may be the one you intend goes as follows.

Definition: Let $g$ be an integer. We say that $g$ is a small primitive root of $p$ if $1\le g<p$ and $g$ is a primitive root of $p$.

The following little result gives some information about your question:
Let $p$ be a prime of the form $4k+1$. Then there is a small primitive root of $p$ which is also a primitive root of $p^2$.

Proof: Let $g$ be a primitive root of the odd prime $p$. Suppose also that $g$ is not a primitive root of $p^2$. This is the case iff $g^{p-1}\equiv 1\pmod{p^2}$.

If $p$ is of the form $4k+1$, then $-g$ is also a primitive root of $p$, and $(-g)^{p-1}\equiv 1\pmod{p^2}$. But then $p-g$ is a primitive root of $p^2$.

Thus for any small primitive root $g$ of a prime of the form $4k+1$, at least one of $g$ or $p-g$ is a primitive root of $p^2$.

Added: The OP in a comment asked for a proof that if $g$ is a primitive root of $p$, then exactly one of $g+kp$ ($0\le k \le p-1$) fails to be a primitive root of $p^2$. A detailed proof is much too long for a comment, so we added it to the above answer. I have not seen the result proved explicitly, but the proof is almost the same as the usual proof that at least one of $g$ and $g+p$ is a primitive root of $p^2$.

By a counting argument, there are $\varphi(p-1)$ numbers, pairwise incongruent modulo $p^2$, which are primitive roots of $p$ but not of $p^2$. So it will be enough to show that no two of these are congruent modulo $p$.

Suppose to the contrary $g_1$ and $g_2$ are primitive roots of $p$, but not of $p^2$, are incongruent modulo $p^2$, but congruent modulo $p$. Then $g_2=g_1+lp$ for some integer $l$.

Since the $g_i$ are not primitive roots of $p^2$, but are primitive roots of $p$, they have order $p-1$ modulo $p^2$. Thus $g_1^{p-1}\equiv g_2^{p-1}\equiv 1 \pmod{p^2}$. By the Binomial Theorem, $$g_2^{p-1}=(g_1+lp)^{p-1}\equiv g_1^{p-1}+(p-1)(lp)g_1^{p-2}\pmod{p^2}.\tag{\ast}$$ But since each of $g_2^{p-1}$ and $g_1^{p-1}$ is congruent to $1$ modulo $p^2$, it follows that $(p-1)(lp)g_1^{p-2}$ is divisible by $p^2$. Thus $l$ is divisible by $p$, and therefore $g_1$ and $g_2$ are congruent modulo $p^2$, contrary to assumption.

We need not have used a counting argument to prove existence from uniqueness. The relationship $$g_2^{p-1}\equiv g_1^{p-1}+(p-1)(lp)g_1^{p-2}\pmod{p^2}$$ can be used directly to show that for any primitive root $g_1$ of $p$, there is an $l$ such that $g_1+lp$ is not a primitive root of $p^2$. It is just a matter of solving the appropriate congruence, like in the proof of Hensel lifting.

-
Thanks for the very informative answer. It seems that I have a bit of exploration to do before fully returning to this problem. If it is not too much trouble, could you perhaps provide me with a reference/proof of the first result you stated? (Exactly one of the numbers $g + kp$ is not a primitive root of $p^2$). Thanks again. –  EuYu Apr 9 '12 at 16:10
@EuYu: It was too messy to write it up in a comment, so I did what you asked for in an addition to the answer. I hope it is clear. If you are familiar with the proof that one at least of $g$ and $g+p$ is a primitive root of $p^2$, it should not be hard. –  André Nicolas Apr 9 '12 at 17:24
Thank you very much André. It is much appreciated. –  EuYu Apr 9 '12 at 18:07