Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
5  
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
3  
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
1  
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
add comment

1 Answer 1

up vote 4 down vote accepted

$\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: enter image description here

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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