Question

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!

Answer 1

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.

Answer 2

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:

Answer 3

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

Answer 4

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.