Number of solutions for pair of discrete logarithm like equations?

Is it possible to show that for given $m$ and $k$, number of primes $p$ for which exists $n$ $(<p)$ satisfying: $$n^m + k\equiv 0\pmod{p}$$ $$(n+1)^m + k\equiv 0\pmod{p}$$ is bounded (finite)?

-
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$ (when $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 :) – Zev Chonoles Aug 7 '11 at 13:33
@Zev: To be honest, I took problem from codegolf.stackexchange.com/questions/1929/…. I worked out for m=2, but I didn't think that m=1 is a case, so I didn't work on it :-) Tnx – Ante Aug 7 '11 at 19:20
@Zev, that $k=1/4$ should be $k=-1/4$, no? – Gerry Myerson Aug 8 '11 at 6:16
@Gerry: Ah, you're right. – Zev Chonoles Aug 8 '11 at 10:58

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.