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?

  • $\begingroup$ Perhaps induction on the degree of the polynomial? You'd need to assume that the degree is at least one, of course. $\endgroup$ – Gary Moon Mar 20 '19 at 13:42
  • $\begingroup$ Perhaps the answer there will help you: math.stackexchange.com/questions/601526/… $\endgroup$ – 77and33is100 Mar 20 '19 at 14:37
  • $\begingroup$ 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? $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ How exactly can you use the Chinese Remainder Theorem in the last step? $\endgroup$ – Mee98 Mar 20 '19 at 16:29
  • $\begingroup$ @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.) $\endgroup$ – Yong Hao Ng Mar 20 '19 at 16:45
  • $\begingroup$ 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$. $\endgroup$ – Yong Hao Ng Mar 20 '19 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.