# Is my proof to this number theory question valid?

I had the following question:

Does there exist a nonzero polynomial $$P(x)$$ with integer coefficients satisfying both of the following conditions?

• $$P(x)$$ has no rational root;
• For every positive integer $$n$$, there exist an integer $$m$$ such that $$n$$ divides $$P(m)$$.

I created a proof showing that there was no polynomial satisfying both of these conditions:

Suppose that we have a nonzero polynomial with integer coefficients $$P(x)=\sum_i c_i x^i$$ without a rational root, and for all positive integer $$n$$, we have an integer $$m_n$$ such that $$n|P(m_n)$$. This would imply $$P(m_n)\equiv0\pmod n\Rightarrow \sum_i c_i m_n^i\equiv0$$. By Freshman's Dream we have $$P(m_n+an)=\sum_i c_i(m_n+an)^i\equiv\sum_i c_im_n^i+c_ia^in^i\equiv\sum_ic_im_n^i=P(m_n)\equiv0\pmod n$$ for some integer $$a$$. Therefore if $$b\equiv m_n\pmod n$$ then $$P(b)\equiv P(m_n)\equiv0\pmod n$$.

Now the above conditions and findings imply for all prime $$p$$, we have a number $$m_p$$ such that $$p|P(m_p)$$, and that if $$b\equiv m_p\pmod p$$ then $$P(b)\equiv 0\pmod p$$. Consider the set of the smallest $$n$$ primes $$\{p_1,p_2,p_3,\cdots,p_n\}$$. By Chinese Reamainder Theorem there exists an integer $$b$$ such that $$b\equiv m_{p_1}\pmod{p_1},b\equiv m_{p_2}\pmod{p_2},b\equiv m_{p_3}\pmod{p_3},\cdots,b\equiv m_{p_n}\pmod{p_n}$$ by Chinese Remainder Theorem. Then $$p_1,p_2,p_3\cdots,p_n|P(b)\Rightarrow p_1p_2p_3\cdots p_n|P(b)$$. As $$n$$ approaches infinity (as there are infinitely many primes), $$p_1,p_2,p_3\cdots,p_n$$ approaches infinity. Therefore either $$P(b)=\infty$$ or $$P(b)=0$$. Since for finite $$b$$ and integer coefficients $$P(b)$$ must be finite, then $$P(b)=0$$. However as $$a$$ is an integer, this implies $$P$$ has a rational root, a contradiction.

I'm not sure if my proof is correct, and my main concern is that I am incorrectly using Chinese Remainder Theorem since I am not sure if I can apply it to infinitely many divisors.

Is this proof correct, and if not, how do I solve this question?

EDIT: It appears not only is my proof incorrect (as$$b$$ does not converge) as Paul Sinclair has shown, but that according to Jaap Scherphuis there are examples of polynomials that satisfy the conditions. Therefore, my question now is how one can prove the existence of these polynomials while using elementary methods (as this is an IMO selection test problem).

• Such polynomials do exist: www2.math.technion.ac.il/~sonn/daniel_Thesis.pdf Nov 25, 2020 at 8:54
• @JaapScherphuis The question was from an International Mathematics Olympiad selection test, it should not require Galois fields to solve.
– Kyky
Nov 25, 2020 at 9:39
• @Kyky - you miss the point. If such polynomials do exist, then your proof that they do not must be flawed. Nov 25, 2020 at 14:35

Your definition of $$b$$ depends on $$n$$. So it is not a constant $$b$$, but rather each $$n$$ has its own $$b_n$$. And it is not the case that $$P(b) = \infty$$ or $$P(b) = 0$$, but instead $$\lim_{n\to\infty} P(b_n) = \infty\text{ or }\lim_{n\to\infty} P(b_n) = 0$$ But this completely spoils your conclusion. Since you do not have a finite fixed $$b$$, you do not have a root $$P(b) = 0$$.

• I see. It has also been shown that such polynomials do exist; do you know how I could prove they exist, preferably without using too advanced methods?
– Kyky
Nov 25, 2020 at 14:56
• I'd have to think about it for a while - spotting a logical flaw in a offered proof is a lot easier than coming up with a proof yourselt. But you are right that it should not require complex topics. However, understand that the thesis in Japp Scherphuis's link is doing a lot more than just proving existence of such polynomials. Nov 25, 2020 at 14:59

Consider the polynomial

$$P(x) = (x^2 - 13)(x^2 - 17)(x^2 - 221)$$

Clearly this has no rational solutions. We wish to show that the congruence $$P(x) \equiv 0 \bmod{m}$$ is solvable for all integers $$m$$. By the chinese remainder theorem, this is the same as showing $$P(x) \equiv 0 \bmod{p^k}$$ is solvable for all prime powers $$p^k$$.

Notice that if either $$13$$, $$17$$, or $$221$$ is a quadratic residue modulo $$p^k$$, then one of the quadratic terms in $$P$$ is a difference of squares modulo $$p^k$$ and factors into linear terms and we are done. We show this is always the case.

For odd $$p \neq 13,17$$, not all of $$13$$, $$17$$, $$221$$ can be quadratic non-residues modulo $$p^k$$, otherwise we would have the following contradiction

$$-1 = \left( \frac{221}{p^k}\right) = \left( \frac{13}{p^k}\right)\left( \frac{17}{p^k}\right)=(-1) (-1)=1$$

If $$p = 13$$ then 17 is a quadratic residue modulo $$p^k$$ because by quadratic reciprocity we have

$$\begin{eqnarray} \left( \frac{17}{13^k}\right) &=& \left( \frac{13^k}{17}\right) (-1)^{\frac{13^k -1}{2} \frac{17 -1}{2}} \\ &=& \left( \frac{13}{17}\right)^k (-1)^{\frac{13^k -1}{2} \frac{17 -1}{2}} \\ &=& 1 \end{eqnarray}$$

If $$p=17$$ a similar argument applies.

For $$p=2$$ we can use Hensel's lemma to show that for any odd $$a$$, $$x^2 \equiv a \bmod{2^k}$$ is solvable for all $$k$$ if and only if $$a \equiv 1 \bmod{8}$$. Therefore $$17$$ is a quadratic residue modulo $$2^k$$ for all $$k$$.

• What about $p=2$ ?? Dec 17, 2020 at 17:19
• @GreginGre of course you're right. I remember this from an exercise in a textbook and it was mainly about using properties of the Legendre symbol, rather than any lifting arguments, but maybe they only asked to prove for odd $m$. I will fix. Thanks.
– JMP
Dec 17, 2020 at 20:22
• You can produce the binary "mod" operator with \bmod. If you want the usual "parenthesis" version, use \pmod. E.g., a\equiv 1\bmod 8 produces $a\equiv 1\bmod 8$. And a\equiv 1\pmod{8} produces $a\equiv 1\pmod{8}$. Dec 17, 2020 at 20:45
• @ArturoMagidin thanks!
– JMP
Dec 17, 2020 at 20:48

Here is an elementary way to construct such a polynomial explicitely. I will need the fact that if $$p\nmid a$$, then $$a$$ is invertible modulo $$p$$, which can be proven using Bézout theorem.

The proof of Fact 1 is extremely long, because i did not want to use group theory but only congruences. It can be shorten into a 5 lines proof if you allow quotient group and the group $$(\mathbb{Z}/p\mathbb{Z})^\times$$.

Fact 1. Let $$p$$ be an odd prime number. Then the number of nonzero squares modulo $$p$$ is $$\dfrac{p-1}{2}$$. In particular, if $$a,b$$ are integrs both prime to $$p$$, then one of the integer $$a,b$$ or $$ab$$ is a square mod $$p$$.

Proof. Set $$m=\dfrac{p-1}{2}$$. An integer coprime to $$p$$ is congruent to some integer $$\pm k$$, where $$1\leq k\leq m$$. Since $$(-k)^2\equiv k ^2 \mod p$$, there is at most $$m$$ nonzero squaremod $$p$$.

Now if $$1\leq k_1,k_2\leq m$$ satisfy $$k_1^2\equiv k_2^2 \mod p$$, then $$p\mid (k_1-k_2)(k_1+k_2)$$. Note that $$2\leq k_1+k_2\leq 2m=p-1$$, so $$p\nmid k_1+k_2$$. Therefore $$p\mid k_1-k_2,$$ meaning $$k_1=k_2$$ since $$-p<-m\leq k_1-k_2\leq m. Consequently, the integrs $$k^2,1\leq \leq m$$ are all distinct modulo $$p$$, and there is exactly $$m$$ non zero square mod $$p$$.

Now let $$a,b$$ be two integers coprime to $$p$$. If $$a$$or $$b$$ is a square modulo $$p$$, we are done. Assume $$a,b$$ are not squares modulo $$p$$. Since $$a$$ is coprime to $$p$$; it is invertible modulo $$p$$, so the elements of $$A=\{a k^2, 1\leq k\leq m\}$$ are pairwise distinct modulo $$p$$. Now the elements $$B=\{k^2, 1\leq k\leq m\}$$ are all distinct modulo $$p$$.

Note that it is not possible to have $$ak_1^2\equiv k_2^2 \mod p$$ for some $$1\leq k_1,k_2\leq m$$, since otherwise $$a$$ would be a square modulo $$p$$, as we can see by multiply by the square of an inverse mod $$p$$ of $$k_1$$.

A counting argument then shows that an integer coprime to $$p$$ can be represented by a unique element of $$A\cup B$$ modulo $$p$$ .

Thus, if $$b$$ is not a square mod $$p$$, then $$b$$ is congruent to an element of $$B.$$ Consequently $$b\equiv a k^2\mod p$$, and $$ab\equiv (ak)^2\mod p$$ is a square mod $$p$$.

Fact 2. Let $$p$$ be a prime number, and let $$P\in\mathbb{Z}[X]$$. Assume that there is $$x_0\in \mathbb{Z}$$ such that $$P(x_0)\equiv 0 \mod p$$ and $$P'(x_0)\not\equiv 0 \mod p$$. Then for all $$m\geq 0$$, there exist $$x_m\in\mathbb{Z}$$ such that $$P(x_m)\equiv 0 \mod p^{m+1}$$ and $$x_{m}\equiv x_0 \mod p.$$

Prof. By induction on $$m$$, the case $$m=0$$ being part of the assumption. Assume that such $$x_m$$ exists for some $$m\geq 0$$ and let us show the existence of some $$x_{m+1}$$. By assumption, $$P(x_m)=\mu p^{m+1}$$. Let $$0\leq \lambda\leq p-1$$ such that $$\lambda$$ is an inverse of $$P'(x_0)$$ modulo $$p$$, and set $$x_{m+1}=x_m-\mu \lambda p^{m+1}$$.

Note that for all $$x,y\in\mathbb{Z}$$, we have $$P(x)=P(y)+(x-y)P'(y)+(x-y)^2 Q(y)$$ for some $$Q\in \mathbb{Z}[X]$$. Applying this to $$x=x_{m+1}$$ and $$y=x_m$$, we get $$P(x_{m+1})=\mu p^{m+1}-\mu\lambda p^{m +1}P'(x_m) \ mod p^{m+2}$$.

Since $$x_m\equiv x_0 \mod p$$, we have $$P'(x_m)\equiv P'(x_0) \mod p$$ and thus $$\lambda P'(x_m)\equiv \lambda P'(x_0)\equiv 1 \mod p$$. Consequently $$\lambda p^{m+1}P'(x_m)\equiv p^{m+1} \mod p^{m+2}$$ and $$P((x_{m+1})\equiv 0 \mod p^{m+2}$$. Finalement note that by construction, $$x_{m+1}\equiv x_m \mod p^{m+1}$$, so $$x_{m+1}\equiv x_m \equiv x_0 \mod p$$, which shows this induction step.

Thm. Let $$P=(X^2+X+2)(X^2-17)(X^2-19)(X^2-17\times 19)$$. Then $$P$$ has no rational roots, but has a root modulo $$n$$ for every integer $$n\geq 2$$.

Proof. Clearly, $$P$$ has no rational roots. By CRT, it is enough to prove that $$P$$ has a root modulo $$p^m$$ for all prime $$p$$ and all $$m\geq 1$$.

Note that $$1$$ is a root of $$X^2+X+1$$ mod 2. The derivative at $$1$$ of this polynomial is $$3$$, which is $$\not\equiv 0 \mod 2$$. Hence $$X^2+X+1$$. has a root mod $$2^m$$ for all $$m\geq 1$$ by Fact 2.

Let $$p$$ be an odd prime number, $$p\neq 17,19$$. By Fact $$2$$, one of the integers $$17,19,17\times 19$$ is a nonzero square mod $$p$$. Let $$a$$ be this integer. Notice now that the derivative of $$X^2-a$$ at an integer $$x_0$$ which is nonzero $$p$$ is $$2x_0$$, which is also nonzero modulo $$p$$. By Fact 2, $$X^2-a$$ has a root mod $$p^m$$ for all $$m\geq 1$$.

Assume that $$p=17$$. Then $$6^2\equiv 19 \mod 17$$, so $$X^2-19$$ has a root mod $$p$$, hence mod $$p^m$$ for all $$m\geq 1$$ as previously.

Assume that $$p=19$$. Then $$6^2\equiv 17 \mod 19$$, so $$X^2-17$$ has a root mod $$p$$, hence mod $$p^m$$ for all $$m\geq 1$$ as previously.

All in all $$P$$ has a root modulo $$p^m$$ for all prime $$p$$ and all $$m\geq 1$$.

• I would advice against using \mod; the spacing is wrong. For the binary operator, use \bmod; for the usual congruence relation with the mode in parentheses, use \pmod. Compare 6^2\equiv 17\mod 19, what you write, which yields $6^2\equiv 17\mod 19$, with 6^2\equiv 17\bmod 19, which produces $6^2\equiv 17\bmod 19$ (cf. the spacing); and 6^2\equiv 17\pmod{19} which gives you $6^2\equiv 17\pmod{19}$. Dec 17, 2020 at 20:51