Prove that if $n \mid 1 + \sum_{k=0}^{n-1} k^{n-1}$ then $n$ is prime. How can I show that if $$n \mid 1 + \sum_{k=0}^{n-1} k^{n-1}$$ then $n$ is prime?
I was able to prove that $n$ must be squarefree as follows: since $n \mid 1 + \sum_\limits{k=0}^{n-1} k^{n-1}$ then $\sum_\limits{k=0}^{n-1} k^{n-1} \equiv -1 \pmod n.$ Suppose some prime $p \mid n$, and let $q = n/p$. Now $\sum_\limits{k=0}^{n-1} k^{n-1} \equiv -1 \pmod p$, so
$$\sum_{k=0}^{n-1}k^{n-1} = \sum_{m=0}^{q-1}\sum_{k=0}^{p-1}(mp+k)^{n-1} \equiv \sum_{m=0}^{q-1}\sum_{k=0}^{p-1}k^{n-1} = q\sum_{k=0}^{p-1}k^{n-1} \equiv -1 \pmod p.$$
Since $-1$ is a unit in $\mathbb Z/p\mathbb Z$, then so must be $q$, so since $p$ is prime we have $p \nmid q$, and thus $p \mid n$ but $p^2 \nmid n$.
I have not been able to show that $n$ must be prime. By reducing exponents using Fermat's Little Theorem, I can show that for every prime $p \mid n$ (again $q = n/p$) we have
$$q \sum_{k=0}^{p-1} k^{q-1} \equiv -1 \pmod p$$
but I am not sure how to deduce (if it is even possible) that for some $p \mid n$ we must have $q = 1$ (which would immediately imply $n = p$).
 A: EDIT 2: This answer is wrong, and in fact the question is an open conjecture of Giuga.     

In particular, the statement
$$\prod_{i \in I} q_i = n^{s-1} \prod_{i \not\in I} p_i$$
is simply completely false; it should instead say
$$\prod_{i \in I} q_i = n^{\left|I\right| - 1} \prod_{i \not\in I} p_i,$$
but then this does not allow us to simply the big sum to reach $1 \equiv 0 \pmod n$.
EDIT: the entire question may be readily generalized, since nowhere do we actually apply the fact that the problem involves powers of $k$. Indeed, suppose $f : \mathbb Z \to \mathbb Z$ is such that for every prime $p$, if $a \equiv b \pmod p$ then $f(a) \equiv f(b) \pmod p.$ If $n > 0$ is an integer such that
$$n \mid 1 + \sum_{k=0}^{n-1} f(k)$$
then $n = 1$ or $n$ is prime. To prove this, just use the proof I already have, but change every instance of $k^{n-1}$ to $f(k)$.

I think I have found a solution. Since I already proved that $n$ must be squarefree, let $n = p_1 p_2 \cdots p_t$ with all the $p_i$ distinct primes, and let $q_i = n / p_i$. Since
$$q_i \sum_{k=0}^{p_i-1}k^{q_i-1} \equiv -1 \pmod {p_i}$$
for all $i$, then for all $i$ there is some $m_i \in \mathbb Z$ such that
$$q_i \sum_{k=0}^{p_i-1}k^{q_i-1} + 1 = m_i p_i.$$
Then
$$\prod_{1 \leq i \leq s} \left(q_i \sum_{k=0}^{p_i-1}k^{q_i-1} + 1\right) = \prod_{1 \leq i \leq s} m_i p_i = n \prod_{1 \leq i \leq s} m_i,$$
so
$$\prod_{1 \leq i \leq s} \left(q_i \sum_{k=0}^{p_i-1}k^{q_i-1} + 1\right) \equiv 0 \pmod n.$$ Assume $s > 1$ (so $n$ is not prime). We may turn the ugly product above into an even more ugly sum of smaller products:
$$\begin{align*}
0 &\equiv \prod_{1 \leq i \leq s} \left(q_i \sum_{k=0}^{p_i-1}k^{q_i-1} + 1\right) \pmod n \\
&= \sum_{I \subseteq \{1, \ldots, s\}} \left(\prod_{i \in I} q_i \sum_{k=0}^{p_i-1}k^{q_i-1}\right) \left(\prod_{i \not\in I} 1\right) \\
&= \sum_{I \subseteq \{1, \ldots, s\}} \left(\prod_{i \in I} q_i \sum_{k=0}^{p_i-1}k^{q_i-1}\right).
\end{align*}$$
Now consider a product $\prod_{i \in I} q_i$ where $\emptyset \neq I \subseteq \{1, \ldots, s\}$. Since $q_i = n / p_i$, then
$$\begin{align*}
\prod_{i \in I} q_i &= \prod_{i \in I} \prod_{j \neq i} p_j \\
&= \prod_{i \in I} p_i^{s - 1} \prod_{i \not\in I} p_i^s \\
&= \left(\prod_{i \in I} p_i\right)^{s-1} \left(\prod_{i \not\in I} p_i\right)^s \\
&= n^{s-1} \prod_{i \not\in I} p_i.
\end{align*}$$
Now the big ugly sum becomes less ugly:
$$\begin{align*}
0 &\equiv \sum_{I \subseteq \{1, \ldots, s\}} \left(\prod_{i \in I} q_i \sum_{k=0}^{p_i-1}k^{q_i-1}\right) \pmod n \\
&= \left(\prod_{i \in \emptyset} q_i \sum_{k=0}^{p_i-1}k^{q_i-1}\right) + \sum_{\emptyset \neq I \subseteq \{1, \ldots, s\}} \left(\prod_{i \in I} q_i \sum_{k=0}^{p_i-1}k^{q_i-1}\right) \\
&= 1 + \sum_{\emptyset \neq I \subseteq \{1, \ldots, s\}} \left(\prod_{i \in I} q_i \sum_{k=0}^{p_i-1}k^{q_i-1}\right) \\
&= 1 + \sum_{\emptyset \neq I \subseteq \{1, \ldots, s\}} \left(n^{s-1} \prod_{i \not\in I} p_i \prod_{i \in I} \sum_{k=0}^{p_i-1}k^{q_i-1}\right) \\
&= 1 + n^{s-1} \sum_{\emptyset \neq I \subseteq \{1, \ldots, s\}} \left(\prod_{i \not\in I} p_i \prod_{i \in I} \sum_{k=0}^{p_i-1}k^{q_i-1}\right) \\
&\equiv 1 \pmod n.
\end{align*}$$
Since $0 \equiv 1 \pmod n$, then $n = 1$.
Therefore if $n \mid \sum_\limits{k=0}^{n-1} k^{n-1}$ then $n$ is one or prime.
