Fifth powers modulo a prime - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T17:53:31Z http://mathoverflow.net/feeds/question/78270 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/78270/fifth-powers-modulo-a-prime Fifth powers modulo a prime Andres Caicedo 2011-10-16T16:02:32Z 2011-10-18T20:07:26Z <p>This is related to Victor Protsak's approach to <a href="http://mathoverflow.net/questions/26358/can-we-color-z-with-n-colors-such-that-a-2a-na-all-have-different-colors" rel="nofollow">this question</a>. </p> <blockquote> <p>Suppose that $p\gt 11$ is a prime of the form $5n+1$. Can we prove that $1^5,2^5,\dots,n^5$ <em>cannot</em> be pairwise different modulo $p$?</p> </blockquote> <p>I ran a quick computer search, and this is indeed the case for $p\le 5\times 42806+1=214031$. In fact, <code>$|\{ i^k\pmod p: 1\le i\le n\}|/n$</code> stays rather close to 0.672...</p> <p>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 <code>$[1,n]$</code>. But then $(x+1)^2=-3$ so $x^3=8$, or $(2x+1)^2=-3$ so $x^3=1$.</p> <p>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$. </p> <p>(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.)</p> http://mathoverflow.net/questions/78270/fifth-powers-modulo-a-prime/78377#78377 Answer by GH for Fifth powers modulo a prime GH 2011-10-17T19:13:45Z 2011-10-17T19:13:45Z <p>Following Darij Grinberg's comments I obtained</p> <p><strong>Theorem.</strong> 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$.</p> <p><strong>Proof.</strong> 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 <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa50/aa5033.pdf" rel="nofollow">here</a>) 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$.</p> http://mathoverflow.net/questions/78270/fifth-powers-modulo-a-prime/78413#78413 Answer by Noam D. Elkies for Fifth powers modulo a prime Noam D. Elkies 2011-10-18T02:44:39Z 2011-10-18T20:07:26Z <p>[<em>Edited to describe triple and higher-order coincidences for prime $k$, recovering the observed $0.672$ proportion for $k=5$</em>]</p> <p>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 &lt; a &lt; b &lt; 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 &lt; p/k \rbrace$. For example, when $k$ is an odd prime, the proportion of $k$-th powers that <em>do not</em> 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 <em>with</em> 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)$.</p> <p>Here's how to estimate the number of pairs. Begin with the observation that $a^k = b^k$ <strong>iff</strong> $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 <code>$0&lt;a,b&lt;p/k$</code>. 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)$.</p> <p>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 <code>$j&lt;k$</code> 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)$. </p> <p>The same technique also works for $0 &lt; a &lt; b &lt; 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 href="http://mathoverflow.net/questions/77986" rel="nofollow">a few days ago</a>).</p>