8
$\begingroup$

Calculate for every positive integer $n$ and for every prime $p$ the expression $$1^n +2^n + \cdots +(p-1)^n \mod p$$

I need your help for this. I don't know what to do, but I'll show you what I know.

  • Wilson's theorem

  • The identity $X^p-X = \prod_{a \in \mathbb{F}_p-1}(X-a)$

  • $\exists a \in \mathbb{Z}, \ a^2 \equiv -1 \mod p \qquad \iff \qquad p \equiv 1 \mod 4$

Now can you please provide me a hint?

$\endgroup$
7
  • 3
    $\begingroup$ Can you use a primitive root, that is, a generator of the multiplicative group? $\endgroup$
    – André Nicolas
    Commented Oct 1, 2013 at 19:45
  • 1
    $\begingroup$ Hint: Do the case $n\equiv 0 \pmod{p-1}$ separately from the rest. $\endgroup$
    – Calvin Lin
    Commented Oct 1, 2013 at 19:55
  • $\begingroup$ Beyond what was already said, please note that there's a mistake in the expression found for $f(1,p)$. $\endgroup$
    – Jonathan Y.
    Commented Oct 1, 2013 at 19:59
  • $\begingroup$ @KoenvanDuin: $kp\equiv0\pmod p$ for every integer $k$. Especially for $k=\frac12(p-3)$. $\endgroup$
    – Bart Michels
    Commented Oct 1, 2013 at 20:17
  • $\begingroup$ I did the case $n \in (p-1) \mathbb{Z}$ seperate from the rest using André's hint, and obtained that the expressions equals $p-1$ in that case, but I don't see how I could use this. COuld you tell me a little more? $\endgroup$
    – Koenraad van Duin
    Commented Oct 2, 2013 at 7:13

5 Answers 5

Reset to default
8
$\begingroup$

Hint: If $a^n \equiv 1 \pmod{p}$ for all $1 \leq a \leq p-1$ you know what the sum is.

Otherwise, if $a^n \neq 1 \pmod{p}$ for some $a$, then use the fact that $\{ a, 2a, 3a, .., (p-1)a \} = \{1,2,3,.., p-1\} \pmod{p}$. Thus

$$ 1^n +2^n + \cdots +(p-1)^n =a^n +(2a)^n + \cdots +[(p-1)a]^n \\ = a^n \left( 1^n +2^n + \cdots +(p-1)^n \right) \pmod{p}$$

You also need to figure out for which $n$ you have $a^n \equiv 1 \pmod{p}$ for all $1 \leq a \leq p-1$...

$\endgroup$
3
  • $\begingroup$ Hmm... your answer appears to be correct in ways that makes my answer incorrect. I'm having trouble figuring out why my answer is wrong... Or is it perhaps that my answer simply fails for those $n$ when $a^n\equiv 1$(mod $p$)? $\endgroup$
    – abiessu
    Commented Oct 1, 2013 at 20:52
  • 1
    $\begingroup$ @abiessu Things are a little more complicated in the even case, the odd case is pretty simple, and your answer is the best approach in that case. Now, in general $a^n \equiv 1 \pmod{p}$ for all $a$ implies $n$ is divisible by $p-1$ (hence Calvin's hint). Thus it follows immediately that for all $n$ excepting multiple of $p-1$ the sum has to be zero. And, UNLESS $p=2$, $p-1|n$ implies $n$ even, which is why this proof doesn't contradict your proof, again UNLESS $p=2$, in which case your proof is wrong ;) $\endgroup$
    – N. S.
    Commented Oct 1, 2013 at 21:17
  • $\begingroup$ Just verifying, did you mean $\{ a, 2a, 3a, .., (p-1)a \} = \{1,2,3,.., p-1\} \pmod{p}$? If the sum only goes up to $(p-a)$ then I think you have some congruence classes missing... $\endgroup$
    – abiessu
    Commented Oct 2, 2013 at 18:36
2
$\begingroup$

From Fermat's little theorem, $x^{p-1}-1=0 \mod p$. From Vieta, this means that all the elementary symmetric polynomials in the x's of order less than p-1 must equal zero mod p. Thus any symmetric polynomial in the x's of order less tha p-1 must equal zero mod p. Is it really that simple, or am I missing something?

$\endgroup$
2
  • $\begingroup$ You are using the fact that every symmetric pol can be expressed as a polynomial in elementary pols, but what if this polynomial had non-zero constant term? $\endgroup$
    – Sil
    Commented Feb 6 at 13:11
  • $\begingroup$ I suspect that proving the constant term of that polynomial is zero mod $p$ is equivalent to the original problem, that would make this answer a circular argument. $\endgroup$
    – Sil
    Commented Feb 7 at 8:52
1
$\begingroup$

Hint:

Consider the reordered sum:

$$1^n+(p-1)^n+2^n+(p-2)^n+...+\left({p-1\over2}\right)^n+\left({p+1\over2}\right)^n$$

For $p=2$, the sum resolves to $1^n$. To see other values it would take on, assume $p\gt 2$.

If $n=1$, then the sum is the well-known binomial $\binom{p-1}2={(p-1)(p-2)\over 2}\equiv 1\mod p$. This should be a good start for induction or direct proof for odd $n$. Can you analyze the sum further and complete it for even $n$?

$\endgroup$
0
$\begingroup$

I don't see the simple answer plainly stated so I will state it here. For $p=2$, the only term in the sum is $1^n$ which is identified in a previous answer as $\equiv 1 \bmod 2$, but for consistency with the larger scheme of things, might better be stated as $\equiv -1 \bmod 2$

For odd $p$ and odd $n$, there are an even number (i.e., $p-1$) of addends, and the sum may be arranged as $1^n+(-1)^n+2^n+(-2)^n+\dots \equiv 0 \bmod p$

If $n$ is even, and if $(p-1)\mid n$, then every addend is a $(p-1)$ power of an integer, so every addend is $\equiv 1 \bmod p$ and the $(p-1)$ addends sum to $(p-1)\equiv -1 \bmod p$

If $n$ is even, and $p\equiv 1 \bmod 4$, and if $(p-1)\not \mid n$, then since quadratic residues in this case come in pairs $a, (p-a)$, the sum is $\equiv 0 \mod p$

If $n$ is even, and $p\equiv 3 \bmod 4$, and if $(p-1)\not \mid n$, I am without a proof, but empirically for several small primes, the sum is $\equiv 0 \mod p$

Overall, if $(p-1)\mid n$, the sum $\equiv -1 \bmod p$; otherwise, the sum $\equiv 0 \bmod p$

$\endgroup$
-1
$\begingroup$

Take the group $G=(\mathbb{Z}_{p},\cdot)$ with the multiplication. Since $p$ is prime then the order of $G$ is $p-1$. Then using $n=k(p-1)$ and $p-1=-1 \pmod p$.

$1^n +2^n +...+(p-1)^n=1+1+...+1=p-1=-1 \pmod p$

$\endgroup$
1
  • 1
    $\begingroup$ This answer isn't correct. $\endgroup$
    – qwr
    Commented Jul 14, 2018 at 20:27

You must log in to answer this question.

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