Suppose we are given a rational function with numerator and denominator being polynomials with integer coefficients. Is there an efficient algorithm for finding all integers arguments at which the function takes integer values?
In other words, for given polynomials $F(x)$ and $G(x)$ with integer coefficients, how to compute efficiently all such integers $m$ that $G(m)$ divides $F(m)$ ?
I've developed a rather straight forward approach to this problem at
http://list.seqfan.eu/pipermail/seqfan/2010-April/004339.html
but I suspect it is far from optimal.
Best Answer
Some closely related (but not algorithmic) results are discussed in this paper of Corvaja and Zannier -- they have a number of other papers over the last few years on the same subject.