Polynomial and prime factors

659 Views Asked by At

So I've been thinking about this questions for ages but I haven't made any progress on it.

I need to prove that for every $f(X) \in \mathbb{Z}[X]$ with $f(0) = 1$, there exists a $n \in \mathbb{Z}$ such that $f(n)$ is divisible by at least 2019 distinct primes.

The only thing that I've seen is that this is easy to show when $f(X)$ has a root in $\mathbb{Z}$ but for the rest I haven't made any progress?

Does anyone know how I can solve this?

1

There are 1 best solutions below

3
On BEST ANSWER

Suppose you know $f(x)$ has a root $r_i$ modulo a prime $p_i$, for $m$ different such primes.

Let $P_m$ be the product of the $m$ primes.

Then since $f(0) = 1$, this tells you that $$ f(kP_m) \equiv 1\not\equiv 0 \pmod{ p_i} $$ for any integer $k$. So none of the existing $m$ primes divide this.

By choosing $k$ large enough, this is not zero (since a polynomial only have finitely many roots) and therefore it must have a prime factor $p_{m+1}$ not the same as the current $m$ you have found. Thus you get a new root $kP_m$ and prime $p_{m+1}$. i.e. $$ f(kP_m) \equiv 0 \pmod{p_{m+1}} $$

So you can find solution to $$ f(r_i) \equiv 0 \pmod{p_i} $$ for arbitrarily many primes $p_i$.

Finally, you can use Chinese Remainder Theorem to find a common root $r$ for all these primes. So that $f(r)$ will be divisible by each of the $p_i$.