# Polynomial and prime factors

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?

• Perhaps induction on the degree of the polynomial? You'd need to assume that the degree is at least one, of course. – Gary Moon Mar 20 '19 at 13:42
• I don't really see how that answer can help me? Like, I don't know which primes divide my function divides and they also don't need to be the same for every value? – Mee98 Mar 20 '19 at 14:46

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$$.

• How exactly can you use the Chinese Remainder Theorem in the last step? – Mee98 Mar 20 '19 at 16:29
• @Mee98 The CRT system to solve is $$r \equiv r_i \pmod{p_i},$$ since if $r_i$ is a root mod $p_i$, then any $r \equiv r_i \pmod{p_i}$ is also a root. Alternatively, if we have $f(r) \equiv 0\pmod A, f(s) \equiv 0\pmod B$ then we can set $k \equiv (s-r)A^{-1}\pmod B$ to get $$f(r+kA)\equiv 0 \pmod{AB}$$, then repeat. (Adding one prime at a time to the product.) – Yong Hao Ng Mar 20 '19 at 16:45
• which works since $$f(r+ kA)\equiv f(r)\equiv 0 \pmod A$$ and $$f(r+kA) \equiv f(r + (s-r)A^{-1}A) \equiv f(r +(s-r))\equiv f(s) \equiv 0\pmod B$$So divisible by $A$ and $B$ means divisible by $AB$. – Yong Hao Ng Mar 20 '19 at 16:50