Take the 2-minute tour ×

This is related to Victor Protsak's approach to this question.

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

share|improve this question
This is probably wrong or otherwise too easy: If the powers $1^5$, $2^5$, ..., $n^5$ would be distinct modulo $p$, then they would be a list of all $5$-th powers modulo $p$ (since $p=5n+1$, so there are only $n$ $5$-th powers modulo $p$), so their sum would be the sum of all distinct $5$-th powers modulo $p$, and that latter sum is known to be $\equiv 0\mod p$ (see artofproblemsolving.com/Forum/viewtopic.php?t=40171 ). In other words, we would have $1^5+2^5+...+n^5\equiv 0\mod p$. But $1^5+2^5+...+n^5=\frac{1}{12}n^2\left(n+1\right)^2\left(2n^2+2n-1\right)$, and some ... –  darij grinberg Oct 16 '11 at 16:58
As $-1$ has to be a $5$-th power, you need the prime $p$ to be a fifth power plus $1$. –  j.p. Oct 16 '11 at 17:00
... polynomial division shows that each of $n$, $n+1$ and $2n^2+2n-1$ is coprime to $5n+1=p$ unless $p=11$. –  darij grinberg Oct 16 '11 at 17:01
Oh, of course, it is clear that for every $k$, it will work for all but finitely many values of $n$, unless the polynomial $kn+1$ divides the polynomial $1^k+2^k+...+n^k$. The question is when this happens, and what are the finitely many values of $n$ otherwise. –  darij grinberg Oct 16 '11 at 17:42
@darij Experimental fact (i.e., SAGE-supported conjecture): Let $f(x,k)$ be the polynomial interpolation of $1^k + 2^k + \cdots + x^k$. Then $k^{k+1}f(-1/k,k)$ is 1 mod $k$ when $k$ is odd and $(k-2)/2$ mod $k$ when $k$ is even. –  Greg Kuperberg Oct 17 '11 at 17:55
show 9 more comments

2 Answers

up vote 12 down vote accepted

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

share|improve this answer
But it does seem that Darij is too modest. –  Greg Kuperberg Oct 17 '11 at 19:23
Great! Many thanks for both the answer and the reference. I'll accept this in a few hours. Meanwhile, a master's student is writing a note on a series of related topics. Would you mind emailing me your name (caicedo@math.boisestate.edu) so we can attribute the result properly? –  Andres Caicedo Oct 17 '11 at 22:01
@Andres: I sent you an email. –  GH from MO Oct 17 '11 at 22:43
add comment

[Edited to describe triple and higher-order coincidences for prime $k$, recovering the observed $0.672$ proportion for $k=5$]

Darij's pretty argument, extended by GH, nicely answers the question for $k$-th powers modulo a large prime $p \equiv 1 \bmod k$ for each fixed $k>2$. Yet more can be said: that approach yields the existence of one coincidence $a^k \equiv b^k$ with $0 < a < b < p/k\phantom.$; but in fact the number of coincidences is asymptotically proportional to $p$: the count is $C_k \phantom. p + O_k(p^{1-\epsilon(k)})$, where $C_k = (k-1)/(2k^2)$ or $(k-2)/(2k^2)$ according as $k$ is odd or even, and $\epsilon(k) = 1/\varphi(k) \geq 1/(k-1)$. Extending the analysis to triple and higher-order coincidences also yields the asymptotic proportion of $k$-th powers that arise in $\lbrace a^k \phantom. \bmod p : a < p/k \rbrace$. For example, when $k$ is an odd prime, the proportion of $k$-th powers that do not have a $k$-th root in $(0,p/k)$ is asymptotic to $((k-1)^k+1)/k^k$; for $k=5$ that's $41/125$, so the proportion with such a $k$-th root is $84/125$, which matches A.Caicedo's observed $0.672$ exactly. It also gives $1 - \frac{8+1}{27} = 2/3$ for $k=3$, matching the proportion of cubes reported by Greg Martin in comments below; as $k \rightarrow \infty$ the proportion of $k$-th powers with small $k$-th roots approaches $1 - (1/e)$.

Here's how to estimate the number of pairs. Begin with the observation that $a^k = b^k$ iff $b \equiv ma \bmod p$ where $m$ is one of the $k-1$ solutions of $m^k \equiv 1 \bmod p$ other than $m=1$. If $k$ is even, we exclude also $m=-1$, which is impossible with $0<a,b<p/k$. Then $b \equiv ma \bmod p$ defines a lattice of index $p$ in ${\bf Z}^2$ all of whose nonzero vectors have length $\gg p^{\epsilon(k)}$, because for such a vector $p$ divides the nonzero number $a^k-b^k$, which factors into homogeneous polynomials in $a,b$ each of degree at most $\phi(k)$. [This is where we use $m \neq -1$: if $a=-b$ then $a^k-b^k=0$.] Thus the solutions of $b \equiv ma \bmod p$ with $a,b \in (0,p/k)$ are the lattice points in a square of area $(p/k)^2$, and their number is estimated by $p^{-1} (p/k)^2 = p/k^2$, with an error bound proportional to (perimeter)/(length of shortest nonzero vector), i.e. proportional to $p^{1-\epsilon(k)}$. The total of $C_k \phantom. p + O_k(p^{1-\epsilon(k)})$ then follows by summing over all $k-1$ or $k-2$ solutions of $m^k=1 \bmod p$ other than $m = \pm 1$, and dividing by 2 because we've counted each coincidence twice, as $(a,b)$ and $(b,a)$.

Likewise one can estimate the counts of triples etc. One must be careful with subsets of the $k$-th roots of unity that have integer dependencies, but at least when $k$ is prime there are no dependencies except that all $k$ of them sum to zero. If I did this right, the result for $j<k$ is that the number of $j$-element subsets of $\lbrace 1, 2, \ldots, (p-1)/k \rbrace$ with the same $k$-th power is asymptotic to ${k \choose j} p / k^{j+1}$, while there are no such subsets with $j=k$ because the sum of all $k$ solutions of $a^k \equiv c \bmod p$ vanishes. An exercise in generatingfunctionological inclusion-exclusion then produces the formula $((k-1)^k+1)/k^k$ for the asymptotic proportion of $k$-th powers that have no $k$-th roots at all in $(0,p/k)$.

The same technique also works for $0 < a < b < M$ with $M$ considerably smaller than $p/k$; and the resulting coincidences, when they exist, can be calculated efficiently using lattice basis reduction (which as it happens I mentioned on this forum a few days ago).

share|improve this answer
Oh, this is really nice! I didn't expect there would be such a clean argument explaining the proportions I had been observing. Many thanks! –  Andres Caicedo Oct 18 '11 at 2:48
I compute $C_5 = 2/25$, so that the proportion of distinct $5$th powers among the first $n$ is $(\frac15-\frac2{25})/\frac15 = 0.6$. How does this match the observed value of $0.672$ from the question (which I duplicated with my own observations)? Both $C_3 = 1/9$ and $C_4=1/16$ (yielding proportions $2/3$ and $3/4$ for $k=3,4$ respectively) do match my observed data, but $k=5$ seems off. –  Greg Martin Oct 18 '11 at 5:06
@Greg Martin: Once $k>4$ the same $k$-th power can arise more than twice. For example, $1^5 \equiv 2^5 \equiv 4^5 \equiv 1 \bmod 31$ yields three $(a,b)$ pairs, and $19^5 \equiv 22^5 \equiv 31^5 \equiv 35^5 \equiv 19 \bmod 181$ yields six. (You can't have all five fifth roots in $(0,p/5)$ because they sum to zero.) –  Noam D. Elkies Oct 18 '11 at 5:33
... and in fact 0.672 is exactly right: the same kind of analysis shows that there are asymptotically $2p/5^3$ triples and $p/5^4$ quadruples, which means that the proportion of fifth powers that arise 0, 1, 2, 3, 4 times is 41/125, 51/125, 26/125, 6/125, 1/125 respectively; and $1 - \frac{41}{125} = \frac{84}{125} = 0.672$ on the nose. –  Noam D. Elkies Oct 18 '11 at 17:50
add comment

Your Answer


