Prove that $p$ divides $ \left(1 ^ {p^ n} + 2 ^ {p^ n} +\cdots+ (p-1)^ {p^ n}\right) $.

Question

Let $p > 2$ be an odd number and let $n$ be a positive integer. Prove that $p$ divides $ \left(1 ^ {p^ n} + 2 ^ {p^ n} +\cdots+ (p-1)^ {p^ n}\right) $.

This is a question from Titu book on number theory and solution straightly goes to below one line. And I have no idea how it resulted.

Define $k = p^n$ and note that $k$ is odd. Then

$$d^k + (p-d)^k = p\left[d ^{(k-1)} - d ^{(k-2)}(p-d) + \cdots+ (p-d)^{(k-1)}\right] $$

Summing up the equalities from $d = 1$ to $d = \frac{p-1}{2}$ implies that $p$ divides $$\left(1 ^ {p^ n} + 2 ^ {p^ n} +\cdots + (p-1)^ {p^ n}\right)$$

Please provide me an intuitive and simple explanation and that I can understand. I found the same question at here but still I am not able to get it.

Answer 1

The idea is that, since $k=p^n$ is odd, $d^k+(p-d)^k$ is divisible by $d+(p-d)=p$.

Thus, $1^k+(p-1)^k, 2^k+(p-2)^k, 3^k+(p-3)^k, ..., $ and $\left(\dfrac{p-1}2\right)^k+\left(\dfrac{p+1}2\right)^k$

are all divisible by $p$, and it follows that the sum

$1^k+2^k+3^k+\cdots\left(\dfrac{p-1}2\right)^k+\left(\dfrac{p+1}2\right)^k+\cdots(p-3)^k+(p-2)^k+(p-1)^k$

is divisible by $p$ as well. Let me know if you need further clarification.

Answer 2

Another way of saying the same thing is to work modulo $p$. Let $S$ denote the sum. Multiplying the numbers $1,2,\cdots,p-1$ by $-1$ is just a permutation modulo $p$. So $-1^{p^n}S\equiv S$ modulo $p$ (the terms of the sum just get rearranged).

On the other hand $-1^{p^n}=-1$, so we have $S\equiv-S$ modulo $p$. Hence $2S\equiv0$ modulo $p$. As $p$ is odd we can divide by 2, to get $S\equiv 0$ modulo $p$, as required.