MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 but I suspect it is far from optimal.

share|cite|improve this question
The reason this problem is messy is that G(x) need not have leading coefficient a unit, so I think some factorization of integers is unavoidable. Where do you think your approach can be improved? – Qiaochu Yuan Jul 1 '10 at 16:39
I don't know what you mean by "compute efficiently", but if $F(x)$ is a constant $N$, and $G(x)=x$, then you're asking how to compute efficiently all the factors of $N$, and this is pretty tough to do efficiently for most reasonable interpretations of the word, as far as I know. – Kevin Buzzard Jul 1 '10 at 16:48
Qiaochu, Kevin, good points. Let us assume that there is small number of solutions and the size of $m$ is reasonable so that we know its complete integer factorization. The case of $G(x)=x$ and $F(x)=N$ is too extreme from this perspective. Usually, $m$ is a number with large number of divisors, only a small fraction of which leads to solutions. And I don't like the idea of brute-forcing them all. – Max Alekseyev Jul 1 '10 at 17:06
@Kevin, Qiaochu: It is still very interesting to find an algorithm with complexity exponential in coefficients but polynomial in degree. I have not seen something of this sort before. – Dror Speiser Jul 1 '10 at 18:06
cf. also my reply to MO question – Noam D. Elkies Nov 26 '12 at 22:07

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.

share|cite|improve this answer

Your Answer


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.