We all know that if $p$ is prime then for $k = p-1$ in $GF(p)$ (field of integers mod $p$) all non-zero elements of the field constitute the full set of $k$-th roots of unity (Fermat's Little Theorem). That is, polynomial $x^k-1$ can be completely factorized in $GF(p)$ as $(x-1)(x-2)...(x-k)$.
Here is the question, which is likely not a simple one (I am hoping less for a quick solution here at SE but rather for a link to an already existing article/solution):
Is it true that for any natural number $k$ there exists a prime number $p > k$ such that $x^k-1$ can be completely factorized in $GF(p)$?
It can be also reformulated thus: given natural number $k$ do there always exist integers $a_1, ..., a_k$ and prime number $p > k$ such that every power sum $a_1^j + ... + a_k^j$ ($1\leq j < k$) is divisible by $p$ while the sum $a_1^k + ... + a_k^k$ is not?
Quick check using SageMath shows this to be true for $k < 200$ with number $k = 197$ being the "worst" of that batch --- the smallest prime $p$ for which $x^k-1$ has $k$ roots in $GF(p)$ is $p = 3547$.
Of course, if $P(x) = x^k-1$ has $k$ roots in $GF(p)$, they cannot repeat (no multiple roots), because $P'(x) = kx^{k-1}$ has only one root which is zero ($k$ is not zero modulo $p$ as $k < p$). This shows that restriction $k < p$ is indeed kind of necessary to prevent obvious examples like $x^{4}-1 = (x-1)^{4}$ in $GF(2)$, or $x^{5}-1 = (x-1)^{5}$ in $GF(5)$.
Ok, so I guess I found the answer to my own question. Solution consists of two rather short steps.
Step 1). Dirichlet Theorem on Arithmetic Progressions guarantees that there is a prime number $p$ of form $km + 1$ (actually it guarantees the existence of infinitely many such primes). So we have a prime $p > k$ such that $p-1$ is divisible by $k$.
Step 2). Multiplicative group $G$ of integers modulo $p$ is cyclic and equals $C_{p-1} = \mathbb Z/(p-1)\mathbb Z$. Since $p-1 = km$ there is a subgroup $H$ of order $k$ consisting of $m$-th powers of all elements of $G$. Obviously, for any element of $H$ its $k$-th power equals 1, and therefore we have $k$ different non-zero residues modulo $p$ all being roots of $x^k-1$ , Q.E.D.
Besides that, for any $k$ and prime $p$, number of $k$-th roots in $GF(p)$ always divides $p-1$ because $k$-th roots of the unity form a subgroup in $G$ -- this means that it is necessary and sufficient for $p$ to have remainder 1 modulo $k$ in order for it to serve as the answer to my question.
Not too hard after all... well, Dirichlet Theorem is not trivial (not by a long shot), but it is a well-known fact in number theory so I guess this closes the question.