Does there exist integer such that there exist sum of powers congruent mod $p$? Let $n \in \mathbb{N}$, $p$ prime. For arbitrary $C \in \mathbb{Z}$, does there exist $a_1, a_2, \dots, a_n \in \mathbb{Z}$ such that$$C \equiv \sum_{i=1}^n a_i^n \text{ }(\text{mod }p)?$$
 A: Let $P_n$ be the set of $n$-th powers $\!\!\pmod{p}$. We have:
$$ |P_n|\geq 1+\frac{p-1}{n} $$
since $\mathbb{F}_p^*$ is a cyclic group and $0$ is always a $n$-th power. By the Cauchy-Davenport theorem:
$$  \underbrace{\left|P_n+P_n+\ldots+P_n\right|}_{n\text{ times}}\geq\min\left(p,n\cdot\left(1+\frac{p-1}{n}\right)-(n-1)\right)=p$$
hence every element of $\mathbb{Z}_{/(p\mathbb{Z})}$ can be represented as the sum of $n$ $n$-th powers.
A: Expanding on Servaes's comment, we provide an alternate solution to the one provided by Jack D'Aurizio.
Let$$X = \{a^n\}, \text{ }kX := \{x_1 + \dots + x_k : x_i \in X\}.$$Observe that $X \setminus \{0\}$ has $(p-1)/n$ elements.
Since$$\{a^n\} = \{a^{\text{gcd}(n,\, p-1)}\},$$it suffices to solve the problem for $n\,\vert\,p-1$.
If $y \in kX$, then $a^ny \in kX$ for any $a$. So $kX \setminus \{0\}$ is a union of cosets of $X \setminus \{0\}$ in the multiplicative group $\mathbb{F}_p^\times$. By induction, at least $m$ cosets of $X \setminus \{0\}$ are in $mX \setminus \{0\}$ for $m \le n$. If $$mX = (m+1)X,$$then$$mX = (m+1)X = (m+2)X = \dots.$$However, $1 \in X$, so $pX$ contains all residues, which means $mX$ contains all residues, and we are done. Otherwise, $(m+1)X$ contains $1$ more coset than $mS$.
Finally, we take $m = n$ to finish.
A: First, we prove this in the case where $n$ divides $p-1$. Consider the polynomial$$P(a_1, a_2, \dots, a_n) = (a_1^n + a_2^n + \dots + a_n^n)(a_1^n + a_2^n + \dots + a_n^n - 1) \dots (a_1^n + a_2^n + \dots + a_n^n - (C-1))(a_1^n + a_2^n + \dots + a_n^n - (C+1)) \dots (a_1^n + a_2^n + \dots + a_n^n - (p-1)).$$(We are taking $C \text{ (mod }p\text{)}$ and turning it into something from $0$ to $p-1$ before doing this.)
Note that the coefficient of $a_1^{p-1}a_2^{p-1} \dots a_n^{p-1}$ in $P$ is nonzero, and $n(p-1)$ is the degree of $P$, so by the Combinatorial Nullstellensatz, there exist integers $m_1, m_2, \dots, m_n$ such that $P(m_1, m_2, \dots, m_n)$ is nonzero modulo $p$, which implies that $m_1^n + m_2^n + \dots + m_n^n$ is congruent to $C$ modulo $p$.
