## Successive nth powers mod p?

While working on a project, I have run into a situation where I have integers x and n so that $x^n \equiv (x+1)^n \equiv (x+2)^n$ mod $p$ for a prime $p$. It seems to me that this an extremely restrictive condition, and I was wondering if there are any results about when (or if?) it can happen, but I couldn't figure out what to search. Any thoughts? What if I add the additional restriction that they are also congruent to $(x+3)^n$, etc.

Thanks!

-
 See cs.umd.edu/~gasarch/res for a link to an article of the Lehmers on runs of residues, as well as other relevant material. – Franz Lemmermeyer Jul 16 2011 at 11:53

## 4 Answers

Write $a = (x+1)/x, b = (x+2)/x$, then your condition is equivalent to $a^n \equiv b^n \equiv 1 \mod p$ and $2a-b \equiv 1 \mod p$. Now, without loss of generality, you can assume $n|(p-1)$ (otherwise replace $n$ by the gcd of $n$ and $p-1$). Write $m = (p-1)/n$ and $a=u^m,b=v^m$. Finally, your conditions become $2u^m-v^m=1$. This defines a curve and, by the Weil bound, it will have points with $uv \ne 0$ if $p \gg m^4$. So, assuming $n|(p-1)$ what you need is $n \gg p^{3/4}$ to guarantee solutions. On the other hand, if $n$ is small, typically there won't be any solutions. If you add the $x+3$ condition, you still get a curve, but of higher genus, so a similar thing will happen with different bounds.

-
Thanks, Felipe. Interestingly, my question is arising from looking at points on curves as well... – dg Jul 15 2011 at 14:35
It appears from Robert Israel's computation below that there are many primes for which there is no solution with $n<\frac{p-1}{2}$. Is there an effective version of this argument showing that these terminate? – Omer Jul 15 2011 at 23:39
that was silly. If p=2q-1 for prime q, then there is no n smaller than q which works. – Omer Jul 15 2011 at 23:47

Of course (if $p \ge 5$) it's true for $n=p-1$ with any $x \in {1,2,\ldots,p-2}$. For the first few primes, the least $n$ for which solutions exist goes as follows:

$$\matrix{ p & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 & 41 & 43 & 47 & 53 & 59 & 61 & 67 & 71 & 73 & 79 & 83 & 89 & 97 & 101 & 103 & 107 & 109 & 113\cr n & - & - & 4 & 6 & 5 & 6 & 8 & 9 & 11 & 7 & 10 & 12 & 8 & 7 & 23 & 13 & 29 & 10 & 22 & 14 & 12 & 26 & 41 & 22 & 24 & 20 & 34 & 53 & 9 & 14\cr}$$

Here is a plot of the pairs $(p, n_{\min})$ for primes up to 541:

-

Here's another approach... one can show for every $n$ there can be solutions for at most finitely many $p$; and for any given $n$ it's not hard to find these $p$ explicitly.

For fixed $n$ the question is when $x^n - (x-1)^n$ and $(x+1)^n - x^n$ can have a common factor (for some integer $x$). Applying the Euclidean algorithm to the two polynomials will yield an integer $N(n)$. For solutions to exist, $p$ must be a factor of $N(n)$, so only finitely many $p$ will do.

(To be perfectly rigorous about this I have to show that the two polynomials have no common factor in $\mathbb{Z}[x]$. But if they did then they would have a common root, say in $\mathbb{C}$. Considering absolute values, we see that the roots of $x^n = (x-1)^n$ all have real part $\frac{1}{2}$ while the roots of $x^n = (x+1)^n$ all have real part $-\frac{1}{2}$. So indeed the polynomials have no common factor, so the Euclidean algorithm will give a constant $N(n)$.

To see that $p$ must divide $N(n)$: the Euclidean algorithm guarantees that $N(n)$ is a linear combination of the two polynomials in $\mathbb{Z}[x]$. So for any value of $x$, $N(n)$ is a linear combination of $x^n - (x-1)^n$ and $(x+1)^n - x^n$. Hence if $x$ is a solution then $N(n)$ is a multiple of $p$.)

A quick calculation by hand gives

N(3) = 2

N(4) = 30

N(5) = 44.

Since $p$ cannot be $2$ or $3$, we see that...

For $n=3$ there are no solutions...

For $n=4$ there are solutions only when $p=5$...

For $n=5$ there are solutions only when $p=11$.

-
 Of course it's easy to adapt this if you want $x$, $x+1$, $x+2$, $x+3$... – Brian Lawrence Aug 1 2011 at 8:39 Instead of using Euclid's algorithm, you can calculate the resultant of the two polynomials. – Gerry Myerson Aug 1 2011 at 12:17

I think van der Waerden's theorem gives at least an arithmetic progression (not consecutive elements) consisting of $n$-th powers. Let $k,n$ be given and $p$ a sufficiently large prime. If $g$ is a primitive root mod $p$, then consider the following coloring of the reduced residue system: $x\mapsto c$ if $x\equiv g^{ny+c}\pmod{p}$ for some $y$ and $0\leq c \lt n$ . This is a coloring of $0,1,\dots,p-1$ with $n$ colors. By van der Waerden's theorem, there is an AP of length $k$, i.e., $y,y+H,\dots,y+(k-1)H$ get the same color, $c$. If we divide by $g^c$, we get an AP $z,z+h,\dots,z+(k-1)h$ of length $k$, consisting $n$-th powers.

-
I don't know what's happening, the system does not accept half of my answer. – Péter Komjáth Jul 16 2011 at 5:38
The system tends to believe that < are the start of html or xml tags. It's better to use \lt or \gt in math mode. – François G. Dorais Jul 16 2011 at 6:18
The larger problem is that the proof is wrong: at the last didivision by $h$, we of course lose the elements being powers. Sorry. – Péter Komjáth Jul 16 2011 at 6:52
Maybe, it is the gap in the proof that caused the system not to accept it? :-) – Seva Jul 16 2011 at 19:35
This argument is fixable for prime $n$ (granted, the Weil bound is much stronger). First, look for a progression of length $Ck$ where $C$ is a very large parameter (something like $n^O(nk)$). Suppose the AP you construct has $h$ which is not a $n$th power: we try to pass to a subprogression with difference $dh$, where $d \le C$. If no $d \le C$ makes $dh$ a $n$th power, there can't be many values of $d \le nk$ that are not $n$th powers (otherwise some product of these must work). But the alternative is that there are so many small $n$th powers that some $k$ must be consecutive. – Erick Wong Jun 15 at 0:25