11
$\begingroup$

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!

$\endgroup$
1

4 Answers 4

26
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks, Felipe. Interestingly, my question is arising from looking at points on curves as well... $\endgroup$
    – user4535
    Jul 15, 2011 at 14:35
  • $\begingroup$ 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? $\endgroup$
    – Omer
    Jul 15, 2011 at 23:39
  • 1
    $\begingroup$ that was silly. If p=2q-1 for prime q, then there is no n smaller than q which works. $\endgroup$
    – Omer
    Jul 15, 2011 at 23:47
6
$\begingroup$

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:

alt text

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Of course it's easy to adapt this if you want $x$, $x+1$, $x+2$, $x+3$... $\endgroup$ Aug 1, 2011 at 8:39
  • $\begingroup$ Instead of using Euclid's algorithm, you can calculate the resultant of the two polynomials. $\endgroup$ Aug 1, 2011 at 12:17
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I don't know what's happening, the system does not accept half of my answer. $\endgroup$ Jul 16, 2011 at 5:38
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 16, 2011 at 6:18
  • 1
    $\begingroup$ The larger problem is that the proof is wrong: at the last didivision by $h$, we of course lose the elements being powers. Sorry. $\endgroup$ Jul 16, 2011 at 6:52
  • 1
    $\begingroup$ Maybe, it is the gap in the proof that caused the system not to accept it? :-) $\endgroup$
    – Seva
    Jul 16, 2011 at 19:35
  • $\begingroup$ 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. $\endgroup$
    – Erick Wong
    Jun 15, 2012 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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