7
$\begingroup$

Is it possible to show that for given $m$ and $k$, number of primes $p$ for which exists $n$ $(

  • 1
    Neat question! I'm sure you've already worked out these cases, but just to mention them: For $m=1$, there are obviously no solutions for any $k$. For $m=2$, $n^2\equiv(n+1)^2\bmod p$ implies $2n+1\equiv 0\bmod p$, to which there is only one solution $n$p\neq 2$), namely $n=\frac{p-1}{2}$. Thus, there are no solutions unless $k=\frac{1}{4}\bmod p$, in which case the sole solution is $n=\frac{p-1}{2}$. The general case probably won't succumb to simple analysis like this though :) – 2011-08-07
  • 0
    @Zev: To be honest, I took problem from http://codegolf.stackexchange.com/questions/1929/greatest-greatest-common-divisor. I worked out for m=2, but I didn't think that m=1 is a case, so I didn't work on it :-) Tnx2011-08-07
  • 0
    @Zev, that $k=1/4$ should be $k=-1/4$, no?2011-08-08
  • 0
    @Gerry: Ah, you're right.2011-08-08

1 Answers 1

1

The two congruences will have a solution if the resultant (q.v.) of the polynomials $x^m+k$ and $(x+1)^m+k$ is a multiple of $p$. For fixed $m$, that resultant is a polynomial in $k$ of degree no more than $m$, so for fixed $k$ it only has a finite number of prime divisors. Thus there will be only a finite number of primes for which the congruences will have a solution.

  • 0
    Still I'm confused about theory background, but it works :-) It is easy to find possible solutions, just check prime factors of Sylvester matrix determinant.2011-08-08
  • 0
    @Ante, if you want, you could always post a new question about the theory. But maybe you'd rather try to work it out yourself, from the literature on resultants.2011-08-09