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.

Given a prime $p$ and a natural number $k$, such that $k$ is not divisible by $p - 1$, prove that $\sum_{i = 1}^{p - 1}i^k \equiv 0 \pmod p$.

I split the proof into two cases: one where $k$ is odd and another where it is even.

The case where $k$ is odd can be proven as follows:

$$\sum_{i = 1}^{p - 1}i^k \equiv \sum_{i = 1}^{\frac{p - 1}{2}}i^k + \sum_{i = 1}^{\frac{p - 1}{2}}(-i)^k \pmod p$$

Since $k$ is odd each $(-i)^k = -i^k$, and will cancel with the positive $i$ leaving a zero. Therefore,

$$\sum_{i = 1}^{p - 1}i^k \equiv 0 \pmod p \text{ if $k$ is odd.} $$

I approached the case where $k$ is even in a similar fashion.

$$\sum_{i = 1}^{p - 1}i^k \equiv \sum_{i = 1}^{\frac{p - 1}{2}}i^k + \sum_{i = 1}^{\frac{p - 1}{2}}(-i)^k \equiv 2(\sum_{i = 1}^{\frac{p - 1}{2}}i^k) \space \pmod p$$

Since $p$ is prime, we just need to prove that $\displaystyle\sum_{i = 1}^{\frac{p - 1}{2}}i^k \equiv 0 \pmod p$.

I was stumped after this, so I considered a counterexample, one where $k$ is divisible by $p - 1$. In that I considered a case where $p = 5, k = 8$:

$$1^8 + 2^8 + 3^8 + 4^8 \equiv 1 + 1 + 1 + 1 \space \pmod p$$

This and a few other cases led to the conjecture that all the numbers below $p$ have a mod cycle $(mod \space p)$ that is divisible by $p - 1$. I tested it with $p = 7$.

$2: 2, 4, {\color{red}1}$

$3: 3, 2, 6, 4, 5, {\color{red}1}$

$4: 4, 2, {\color{red}1}$

$5: 5, 4, 6, 2, 3, {\color{red}1}$

After this I was stuck. I couldn't see how this would help me solve the problem. And, more importantly, I couldn't prove my conjecture.

share|improve this question

3 Answers 3

up vote 2 down vote accepted

HINT:

As $i,1\le i\le p-1$ forms Reduced Residue System $\pmod p,$

and so does $g^r,$ for $0\le r\le p-2$ where $g$ is a primitive root of $p$

$$\text{So, }\sum_{1\le i\le p-1}i^k\equiv\sum_{0\le r\le p-2}(g^r)^k\pmod p$$

$$\text{Now, }\sum_{0\le r\le p-2}(g^r)^k=\frac{(g^k)^{p-1}-1}{g^k-1}=\frac{(g^{p-1})^k-1}{g^k-1}$$

Using Fermat's Little Theorem, $g^{p-1}\equiv1\pmod p\implies (g^{p-1})^k\equiv1\pmod p\iff (g^{p-1})^k-1\equiv0\pmod p$

As $g$ is a primitive root of $p,\text{ord}_pg=p-1\implies g^k\not\equiv1\pmod p$ as $k$ is not divisible by $p-1$

$\implies (g^k-1,p)=1\implies \frac{(g^{p-1})^k-1}{g^k-1}\equiv0\pmod p$

$\implies \sum_{1\le i\le p-1}i^k\equiv\sum_{0\le r\le p-2}(g^r)^k\equiv \frac{(g^{p-1})^k-1}{g^k-1}\equiv0\pmod p$

share|improve this answer

Let $b$ be any number relatively prime to $p$. Recall that the numbers $b, 2b, 3b, 4b, \dots, (p-1)b$ are a reduced residue class modulo $p$. This means that $b,2b,3b,\dots, (p-1)b$ travel, modulo $p$, through $1,2,3,\dots, p-1$ in some order.

It follows that $$b^k+(2b)^k+(3b)^k+\cdots +((p-1)b)^k \equiv 1^k+2^k+3^k +\cdots +(p-1)^k\pmod{p}\tag{1}$$ But $(ib)^k=b^ki^k$, so we can rewrite (1) as $$(b^k-1)\left(1^k+2^k+3^k+\cdots +(p-1)^k\right)\equiv 0\pmod{p}.\tag{2}$$

Let $b$ have order $p-1$ modulo $p$. So we are letting $b$ be a primitive root of $p$. Since $p-1$ does not divide $k$, we have $b^k \not\equiv 1\pmod{p}$. Then it follows from (2) that $1^k+2^k+3^k+\cdots (p-1)^k \equiv 0\pmod{p}$.

share|improve this answer

All nonzero numbers less than p are roots of $x^{p-1}=1$ (mod p). Thus, all the elementary symmetric polynomials in these number of order less than p-1 are zero (mod p), so any symmetric polynomial in these numbers of order less than p-1 must be zero (mod p).

share|improve this answer
    
Really neat! :) –  Rodrigo Jan 18 at 14:35

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.