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$).
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.