# $x^p+y^p$ is a primitive root modulo $p^2$

I can't solve the following problem:

Let $p$ be a prime. Prove that there is a primitive root modulo $p^2$ of the form $x^p+y^p$.

Edit: There was a mistake, i hope now it's correct. Now the problem is very weak but i'm sure it's correct. My apologies if someone wasted his time with this problem.

-
Doesn't work for $p=3$. Modulo $9$, $x^3$ is either $0$, $1$ or $8$. So the possible sums are $0$, $1$, $2$, $7$, $8$. Only $2$ is a primitive root modulo $9$. –  David Speyer Apr 8 '12 at 12:57
Corrected version doesn't for $p=5$: Of the possible sums, $2=1+1$, $17 \equiv 4^5+3^5$, $8 \equiv 1+2^5$ and $23 \equiv 4^5+4^5$ are primitive roots. The strongest true statement I can find is that $\phi(p-1)$ divides the number of such sums that are primitive roots. Where does this problem come from? –  David Speyer Apr 8 '12 at 21:21
@David Speyer A friend of mine gave it to me, i though it was right, i tried it for an hour and couldn't solve it. Could you post your full solution please? i'll post a really weak version of the problem in order to correct it. –  xD13G0x Apr 9 '12 at 2:42
What I know is written below. Let me suggest that, if you have tried to prove something for an hour and can't, you put in five minutes looking for a counterexample. –  David Speyer Apr 9 '12 at 15:14

$\def\ZZ{\mathbb{Z}}$I've thought enough about this problem that I might as well write up an answer summarizing what I know. Let $p$ be an odd prime. Let $U$ be the group of units modulo $p^2$. As I assume you know, $U \cong \ZZ/p(p-1) \cong \ZZ/p \times (\ZZ/p)^{\times}$. Let's call these two factors $S$ and $T$. Explicitly, $S$ is the group of units of the form $1+kp$ and $T$ is the group of units of the form $x^p$.

For example, when $p=5$, the group $S$ is $\{ 1, 6, 11, 16, 21 \}$ and the group $T$ is $\{ 1, 32, 243, 1024 \} \equiv \{ 1, 7, 18, 24 \} \mod 25$. You can have fun checking that each of these really is a subgroup of $(\ZZ/25)^{\times}$.

An element of $U$ is a primitive root if it is not in $T$ and its projection to $T$ is a primitive root.

Let $X \subseteq U$ be the set of units of the form $x^p + y^p$. Notice that, if for $t=z^p \in T$, we have $t (x^p+y^p) = (zx)^p + (zy)^p$. So the set $X$ is invariant under translation by $T$. We see that $(s,t)$ is in $X$ if and only if $(s,t')$ is in $X$. Let $Y \subset S$ be the set of $s\in S$ such that $(s,t)$ is in $X$ for any, or equivalently every, $t \in T$. So $X = Y \times T \subset S \times T = U$.

An element $(s,t)$ in $X$ is a primitive root if and only if $s$ is not the identity of $S$ and $t$ is a primitive root. So the number of primitive roots you are interested in is $| Y \setminus \{ 1 \}| \times \phi(p-1)$.

What's left is to compute the size of $Y$. I can't find a lot to say, but here is a little.

We'll write elements of $S$ as $1+kp$. Such an element is in $X$ if it is of the form $x^p+y^p$ with $x^p + y^p \equiv 1 \mod p$. The latter congruence is equivalent to $x+y \equiv 1 \mod p$. So we have $$1+kp \equiv (1+z)^p - z^p \bmod p^2$$ $$k \equiv \frac{1}{p} \left( \binom{p}{1} z + \binom{p}{2} z^2 + \cdots + \binom{p}{p-1} z^{p-1} \right) \bmod p.$$ So $Y$ is the set of the distinct values of $$f_p(z) := \frac{1}{p} \sum_{j=1}^{p-1} \binom{p}{j} x^j$$ modulo $p$. One can explicitly compute $\frac{1}{p} \binom{p}{j} \equiv \frac{(-1)^{j-1}}{j} \bmod p$ but it doesn't seem to be useful.

$Y$ does contain at least one nonzero value, since $f_p$ only has degree $p-1$, so it can't be identically zero. That answers your request to prove that there is some primitive root of the form $x^p+y^p$. The first few values of $Y$ are $$\begin{array}{r l} p & Y \\ 3 & \{ 0,2 \} \\ 5 & \{0, 1, 2\} \\ 7 & \{0, 4, 5\} \\ 11 & \{0, 1, 6, 7, 10\} \\ 13 & \{0, 5, 6, 7, 9, 10\} \\ \end{array}$$

Here is a plot of $(p, |Y(p)|)$ for the first $100$ odd primes:

The best fit line is $0.40 p + 0.72$. If I were to take a guess, I would guess that $|Y(p)| \approx p/e$ for large $p$. This is because the expected size of the image of a random map $\ZZ/p \to \ZZ/p$ is $\approx p/e$. The numerical fit is so-so, $1/e \approx 0.37$ not $0.40$, but I'm sticking to it until someone gives me a better heuristic.

-