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

Question

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.

Answer 1

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$