It is related to [this](https://mathoverflow.net/questions/92753/sums-of-powers-mod-p)  question. 


 **Question.**  Suppose that $p$ is a prime, $p-1$ is divisible by $q^2$ for some $q$. Is it true that every number modulo $p$ is a sum of two $q$-th powers. 


If $q=2$, then (\*) is true. Indeed in that case $p\equiv 1 \mod 4$. Take any number $t \mod p$. WLOG we can assume that $t$ is odd (the product of two sums of two squares is a sum of two squares). If $t\equiv 1 \mod 4$, then consider the arithmetic progression $4np+t, n\ge 0$. By Dirichlet, it contains a prime $p'\equiv 1\mod 4$. By Fermat, $p'$ is a sum of two squares, hence $t$ is a sum of two squares modulo $p$. If $p\equiv -1 \mod 4$, then consider the arithmetic progression $8np+t-2p, n\ge 0$. By Dirichlet, it contains a prime number $p'$ of the form $4k+1$ (since $p\equiv 1\mod 4$) and we are done. 


That question may be easier than the question cited above. Or it may be a known open problem. 


 **Update**  Several simplifications of the argument for $q=2$ were proposed. Although the statement is not true when $(p-1)/q^2$ is small, it is true when this quotient is large enough. I think this answers my question almost completely. Thanks to everybody who gave an answer or a comment. 



Sums of two same powers modulo $p$
Suppose $p=q^2 + 1$. Then the set of $q$-th powers, including 0, has size $q+1$. The number of elements given by a sum of pairs of these is at most $(q+1) + \frac{(q+1)(q)}{2} = \frac{q^2 + 3q + 2}{2} < q^2 + 1$ whenever $q > 3$. So, for example, $6,7,10,11$ are not expressible as a sum of two fourth powers in $\mathbb{Z}/(17)$.


