Fifth powers modulo a prime - MathOverflow

Fifth powers modulo a prime

2011-10-16T16:02:32Z

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

Answer by GH for Fifth powers modulo a prime

2011-10-17T19:13:45Z

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

Answer by Noam D. Elkies for Fifth powers modulo a prime

2011-10-18T02:44:39Z

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