Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
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 '11 at 11:53
add comment

4 Answers

up vote 25 down vote accepted

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.

share|improve this answer
    
Thanks, Felipe. Interestingly, my question is arising from looking at points on curves as well... –  user4535 Jul 15 '11 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 '11 at 23:39
1  
that was silly. If p=2q-1 for prime q, then there is no n smaller than q which works. –  Omer Jul 15 '11 at 23:47
add comment

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

share|improve this answer
add comment

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

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

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.

share|improve this answer
    
I don't know what's happening, the system does not accept half of my answer. –  Péter Komjáth Jul 16 '11 at 5:38
1  
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 '11 at 6:18
1  
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 '11 at 6:52
1  
Maybe, it is the gap in the proof that caused the system not to accept it? :-) –  Seva Jul 16 '11 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 '12 at 0:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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