This is related to Victor Protsak's approach to [this question](https://mathoverflow.net/questions/26358/can-we-color-z-with-n-colors-such-that-a-2a-na-all-have-different-colors). 



> 
> Suppose that $p\gt 11$ is a prime of
>  the form $5n+1$. Can we prove that
>  $1^5,2^5,\dots,n^5$ *cannot* be
>  pairwise different modulo $p$?
> 
> 
> 


I ran a quick computer search, and this is indeed the case for $p\le 5\times 42806+1=214031$. In fact, $|\{ i^k\pmod p: 1\le i\le n\}|/n$ stays rather close to 0.672...


It is not hard to answer the same question with 3 in the place of 5: There are no primes of the form $3n+1$ with $1^3,2^3,\dots,n^3$ distinct modulo $p$. Quickly, $-3$ is a quadratic residue of any $p$ of the form $3n+1$. One easily checks that (modulo $p$) there must be a $y$ such that $y^2=-3$ and either $x=y-1\ne 1$ or $x=(y-1)/2\ne 2$ is in the interval $[1,n]$. But then $(x+1)^2=-3$ so $x^3=8$, or $(2x+1)^2=-3$ so $x^3=1$.


If instead of 3 we use a number of the form $4k$, then there are only finitely many primes $p=4nk+1$ for which $1^{4k},\dots,n^{4k}$ are distinct modulo $p$ (but there may be such $p$; for example, if $4k=84$, then we can take $n=5$). This is because there are $x,y$ with $1\le x\lt y$ and $x^2+y^2=p$, so $x^{4k}\equiv y^{4k}\pmod p$, and if $p$ is slightly larger than $(4k)^2$, then $y\le n$. 


(Of course one can ask the same question with any $k$ in the place of $5$, and I suspect that as long as $k>2$, the answer is always that there are only finitely many values of $n$ for which the powers are distinct. But I also suspect that this is going to be significantly harder than for $k=5$. I would be delighted for suggestions or approaches towards this more general case.)



Fifth powers modulo a prime
Following Darij Grinberg's comments I obtained


**Theorem.** For any integer $k>2$ there are only finitely many primes of the form $p=kn+1$ such that $1^k,2^k,\dots,n^k$ are distinct modulo $p$.


**Proof.** Assume that $k,n>2$ and $p=kn+1$ is a prime such that $1^k,2^k,\dots,n^k$ are distinct modulo $p$. Then the list represents the $k$-th powers modulo $p$, a cyclic group of order $n$. As a result, their squares $1^{2k},2^{2k},\dots,n^{2k}$ represent the $2k$-th powers modulo $p$ with multiplicity $1$ or $2$ depending on whether $n$ is odd or even. At any rate, $p$ divides their sum
$$ \sum\_{m=1}^n m^{2k}=\frac{1}{2k+1}B\_{2k+1}(n+1), $$ 
where $B\_{2k+1}(x)\in\mathbb{Q}[x]$ denotes the $(2k+1)$-th Bernoulli polynomial. Here we used $p-1>2k$ and the vanishing of the $(2k+1)$-th Bernoulli number. By a result of Inkeri (see [here](http://matwbn.icm.edu.pl/ksiazki/aa/aa50/aa5033.pdf)) the linear factors of $B\_{2k+1}(x)$ over $\mathbb{Q}$ are $x$, $x-1/2$, $x-1$, hence $x+1/k$ is certainly coprime to $B\_{2k+1}(x+1)$. It follows that there is an integer $N>0$ and polynomials $u(x),v(x)\in\mathbb{Z}[x]$ depending on $k$ such that
$$ u(x)(kx+1)+v(x)B\_{2k+1}(x+1)=N. $$
By plugging $x=n$ we see that $p$ divides $N$, hence $p$ can only take finitely many values depending on $k$.


