Prove that there exists a polynomial with integer coefficients satisfying the following conditions: (a)$f(x)=0$ has no rational root. (b) For any positive integer $n$, there always exists an integer $m$ such that $n\mid f(m)$.
Problem
Source: 2017 Taiwan TST Round 3
Tags: algebra, polynomial
13.04.2018 17:26
Interesting that they put it on a TST; this is a famous problem from PFTB.
13.04.2018 17:35
https://artofproblemsolving.com/community/c6h561917p3275968 Also KMO 2013.
13.04.2018 23:48
$(x^{8}-16)(x^{3}-3)$ works
12.05.2020 09:24
$(x^2-2)(x^2-3)(x^2-6)(x^2-17)(x^2-7)$ works by Legendre symbol and Hensel’s lemma
03.04.2021 11:44
Weird for a TST? Also, this is very famous. $(x^2+1)(x^2+2)(x^2-2)(x^2+7)$ works as well.
29.09.2024 16:03
We claim that \[f(m) = (x^2 + 1) (x^2 - 7)(x^2 + 7) (x^2 + 1434)\]works. Clearly it has no rational roots. Claim: It suffices to show that for all primes $p$ and positive integers $k$, there exists an integer $x$ such that $p^k \mid f(x)$. Proof: Suppose we have shown this. Fix any positive integer $n$. Denote a function $r$ from prime powers to integers so that $p^k \mid f(r(p^k))$ for every prime $p$ and nonnegative integer $k$. Now choose $m$ such that $m \equiv r(p^{\nu_p(n)}) \pmod{p^{\nu_p(n)}}$ for every prime $p$ dividing $n$. This is clearly possible by CRT. Note that clearly $p^{\nu_p(n)} \equiv f(m)$ for any prime $p$ dividing $n$. Hence the product of $p^{\nu_p(n)}$ over primes $p$ dividing $n$ also divides $f(m)$, meaning $n \mid f(m)$, as desired. $\square$ Case 1: $p = 2$ We show that $\nu_2(x^2 + 7)$ is unbounded. Suppose otherwise and $M$ was the maximal possible value of $\nu_2(x^2 + 7)$ over integers $x$. Note that setting $x = 1$ gives that $M \ge 3$. Fix $m$ (odd) with $\nu_2(m^2 + 7) = M$. Consider $x = m + 2^{M-1}$. We have $x^2 + 7 = m^2 + 7 + 2^M \cdot m$. Since $\nu_2(m^2 + 7) = \nu_2(2^M \cdot m) = M$, we have $\nu_2(x^2 + 7) \ge M + 1$ for $x = m + 2^{M-1}$, a contradiction. Thus, $\nu_2(x^2 + 7)$ is unbounded, so the polynomial works for $p = 2$. Case 2: $p \equiv 1 \pmod 4$ Note that we can easily find $x$ where $p \mid x^2 + 1$ since $-1$ is a Quadratic Residue modulo $p$. Now noting that $(x^2 + 1)' \not \equiv 0 \pmod p$ (because $p \nmid x$), we see that applying Hensel's lemma shows that $\nu_p(x^2 + 1)$ is unbounded as $x$ varies. Case 3: $p \equiv 3 \pmod 4$, $7$ is a Quadratic Residue modulo $p$, and $p \ne 7$ Since $7$ is a QR modulo $p$, there exists $x$ with $p\mid x^2 - 7$. Now, $p\nmid x$ clearly as $p \ne 7$. So $p \nmid (x^2 + 7)'$ and we can use Hensel's again to show that $\nu_p(x^2 - 7)$ is unbounded as $x$ varies. Case 4: $p \equiv 3 \pmod 4$ and $7$ isn't a QR modulo $p$ Note that $p \ne 7$. Note that $-7$ is a QR modulo $p$ as $-1$ is a NQR mod $p$. So there exists $x$ with $p \mid x^2 + 7$. We can similarly apply Hensel's as above to show that $\nu_p(x^2 + 7)$ is unbounded as $x$ varies. Case 5: $p = 7$. Note that there exists $x$ with $7 \mid x^2 + 1434$ ($x = 1$). Notice that if $7 \mid x^2 + 1434$, then $(x^2 + 1434)' \not \equiv 0 \pmod 7$ because $7 \nmid x$, so applying Hensel's gives that $\nu_7(x^2 + 1434)$ is unbounded, as desired.