Show for any monic polynomial $p(x)$ and for any $k$ that there are $k$ primes $q_i$ and $k$ integers that $n_i$ such that $q_i|p(n_i)$ Problem: Let $p(x)$ be a monic polynomial with integral coefficients, I want to show using induction for any integer $k$ that there exists $k$ distinct primes $q_1,\ldots,q_k$ and $k$ integers $n_1,\ldots, n_k$ such that $q_i\big|p(n_i)$.
My solution (after struggling with this problem for a couple of hours sigh) which is based on Fermat’s little theorem and Chinese remainder theorem is as follows:
For $k=1$ it is trivial so let’s assume the inductive hypothesis that we have $k$ prime and $k$ integers with the desired property. We want to show that there’s another prime-integer pair $(q_{k+1},n_{k+1})$ such that $q_{k+1}|p(n_{k+1})$.
Now notice that $p(x) \mod q_i$ is equivalent to a $\le \deg q_i-1$ polynomial by Fermat’s little theorem, and so for one of the equivalence classes of $q_i$, $p(x)\not=0\mod q_i$ (Since the number of solutions $\mod q_i$ can not exceed $\deg p(x)\mod q_i$. Hence, by the CRT there’s a positive integer $n$ that satisfies the desired equivalence classes,i.e, $p(n)\not=0\mod q_i$. Therefore, there must be a prime $q_{k+1}$ that divides $p(n)$. 
I think this work but I could be wrong.However, I am not satisfied with this answer since it utilizes polynomials over finite fields which is out of the scope of the chapter I am working on (I may be wrong here as well). Any hints to solve this problem that’s different from my approach? Additionally, the polynomial’s monicity isn’t utilized which tells me that I made a mistake.
 A: Hint. For the $k \Rightarrow k+1$ step you may consider 


*

*if $p(0)=0$, then any $q_{k+1}\notin \{q_1,...,q_k\}$ will satisfy $q_{k+1}\mid p(q_{k+1})$. In this case $n_{k+1}=q_{k+1}$. Otherwise ...

*$p\left(\color{red}{p(0)}\cdot\color{blue}{\prod\limits_{j=1}^k q_j}\right)=\color{red}{p(0)}\cdot\left(\color{green}{Q}\cdot\color{blue}{\prod\limits_{j=1}^k q_j}+1\right)$ ($Q$ some integer) and $Q\cdot\prod\limits_{j=1}^k q_j+1$ will either be prime or divisible by a prime $q_{k+1} \notin \{q_1,...,q_k\}$. In this case $n_{k+1}=p(0)\cdot\prod\limits_{j=1}^k q_j$

The latter is due to
$$p(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0 \Rightarrow \\
p(\color{red}{a_0}\cdot \color{blue}{x})=a_n(a_0\cdot x)^n+a_{n-1}(a_0\cdot x)^{n-1}+...+a_1(a_0\cdot x)+a_0=\\
\color{red}{a_0}\left(\color{blue}{x}\cdot\color{green}{\left(a_n(a_0\cdot x)^{n-1}+...+a_2(a_0\cdot x)+a_1\right)}+1\right)$$
and of course $p(0)=a_0$
A: It's sufficient to prove that there's at least one prime, other than $q_1,\ldots,q_k$, which divides some value taken by the polynomial.
Suppose not, then every value taken by the polynomial is of the form $\pm q_1^{a_1}q_2^{a_2}\cdots q_k^{a_k}$. Can you upper bound the number of integers of this form in the interval $[-m,m]$ as a function of $\log m$?
Now suppose the polynomial has degree $r$, and the maximum modulus of coefficients is $t$. Can you lower bound the number of values it must take in $[-m,m]$? You should be able to do this in such a way that the lower bound is bigger than the upper bound for $m$ sufficiently large, giving a contradiction.
