Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 6 down vote favorite

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)?

share|improve this question
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

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
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. – Ante Aug 8 '11 at 19:38
@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. – Gerry Myerson Aug 9 '11 at 3:39

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.