Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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
17  
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
3  
... 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
1  
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
1  
@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
3  
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
2  
@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
2  
... 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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.