Prove that for all $ n\geq 2,$ there exists $ n$-degree polynomial $ f(x) = x^n + a_{1}x^{n - 1} + \cdots + a_{n}$ such that (1) $ a_{1},a_{2},\cdots, a_{n}$ all are unequal to $ 0$; (2) $ f(x)$ can't be factorized into the product of two polynomials having integer coefficients and positive degrees; (3) for any integers $ x, |f(x)|$ isn't prime numbers.
Problem
Source: Chinese TST
Tags: algebra, polynomial, modular arithmetic, absolute value, algebra proposed
20.04.2008 13:31
For $ n>3$, $ f(x)=x^n+12x^{n-1}+3x^{n-2}+12x^{n-3}+\ldots +12$. It is irreducible due to Eisenstein Criterion and $ 4$ divides $ f(x)$ for all integer $ x$ so it can't be prime. For $ n=3$, $ f(x)=x(x+1)(x+2)+12$. It is irreducible because if it is not it must have an integer root. $ 6$ divides $ f(x)$ for all integer $ x$ so it can't be prime. For $ n=2$, $ f(x)=x^2+x+100$
04.02.2009 19:30
I am not sure I understand the example for $ n > 3$. How is it defined for even $ n$? with 3 as the coefficient of $ x^0$, or 12? Also, why is it divisible by $ 4$? For $ n = 5$, $ f(x) = x^5 + 12x^4 + 3x^3 + 12x^2 + 3x + 12 \equiv x^5 - x^3 - x = x(x^4 - x^2 - 1) \pmod 4$. If we take x=1, we get $ - 1 \equiv 0 \pmod 4$.
05.02.2009 13:22
If $ n=2$, consider $ f(x)=x^2+x+100$. If $ n$ is odd, consider $ f(x)=x^n+21x^{n-1}+21x^{n-2}+\ldots+21x^2+14x+42$. If $ n$ is even and greater than $ 2$, consider $ f(x)=x^n+21x^{n-1}+21x^{n-2}+\ldots+21x^3+14x^2+42x+42$.
02.03.2009 07:37
bambaman, the rest of the coefficients are $ 12$. sorry for this unclear notation.
02.03.2009 07:48
$ f(x) = x^n + 4n x^{n - 1} + 4 x^{n - 2} + ...$ is irreducible by Perron's criterion for $ n \ge 2$.
15.04.2009 12:05
The official solution: Let $ f(x)=x^n+210(x^{n-1}+x^{n-2}+\cdots +x^2)+105x+12$ First $ f(x)$ is irreducible by Eisenstein Criterion for $ P=3$ Second $ f(x)$ is even for all integer $ x$ If $ f(x)=2$ has integer root $ x$, then $ g(x)=x^n+210(x^{n-1}+x^{n-2}+\cdots +x^2)+105x+10$ has integer root, but $ g(x)$ is irreducible by Eisenstein Criterion for $ P=5$, a contradiction. If $ f(x)=-2$ has integer root $ x$, then $ g(x)=x^n+210(x^{n-1}+x^{n-2}+\cdots +x^2)+105x+14$ has integer root, but $ g(x)$ is irreducible by Eisenstein Criterion for $ P=7$, a contradiction, too. So for any integer $ x$, $ f(x)$ is even and its absolute value is not $ 2$, which means $ f(x)$ is a composite number. Q.E.D
20.02.2020 23:34
For $n = 2$ use $f(x) = x^2 + x + 4$. For $n \ge 3$, choose a large prime $q$ and $k$ such that $q| 3k-1, 3k-1 > q^{1778}$. Take $f(x) = x^{n-2}(x^2 -1 + 3k) + 3q$ which is always divisible by $3$. Moreover, by Eisenstein's Criterion on prime $q$, $f$ is irreducible. It suffices to check that $|f(x)|$ is not prime for any integer $x$. Suppose otherwise, then $3|f(x) \implies f(x) = \pm 3$, i.e. $x^{n-2}(x^2 - 1 + 3k) = -3q \pm 3$. This is false for $x = 0$ as we've chosen $3k-1 > q^{1778} > 3q \cdot 1778$. Thus $x \ne 0$. But then the absolute value of LHS is at least $x^2 - 1 + 3k > -1 + 3k > q^{1778} > 3q\cdot 1778$ again, contradiction.
05.08.2023 17:15
Does this work? Case 1: $n$ is even. Consider $a_1 = 239$, $a_2 = a_3 = \cdots = a_{n-1} = 1434$, and $a_n$ is a sufficiently large even multiple of $239$ but not $239^2$ (clearly infinitely many such positive numbers exist). Such a polynomial is irreducible over the integers by Eisenstein with $p=239$. We see that $f(x)$ is always even because $f(0) = a_n\equiv 0\pmod 2$ and $f(1) = 1 + \sum a_i \equiv 0\pmod 2$. It remains to show that $f(x)\ne \{-2,2\}$. Since $f(x) - a_n$ has a lower bound, we may choose $a_n$ large enough such that $f(x) >2$ for any integer $x$. Case 2: $n$ is odd. Consider $a_1 = 69$, $a_2 = 92$, $a_3 = \cdots = a_n = 276$. Such a polynomial is irreducible over the integers by Eisenstein with $p=23$. Now we show that $|f(x)|$ is never prime for any integer $x$. Claim: $f(x)$ is a multiple of $6$ for any integer $x$ Proof: It suffices to show that $2$ divides $f(0)$ and $f(1)$, and also that $3$ divides $f(0), f(1), $ and $f(2)$. We have $f(0) = a_n = 276\equiv 0\pmod 6$. We have $f(1) = 1 + \sum a_i$, which is even because it's equivalent to $1 + a_1 $ modulo $2$, and a multiple of $3$ because it's equivalent to $a_2 + 1 \pmod 3$. We have $f(2) \equiv 2^n + a_2 2^{n-2} \equiv 2 + 2a_2 \equiv 0\pmod 3$, as desired. $\square$ Therefore, $|f(x)|$ is never prime since there are no prime multiples of $6$.
30.08.2023 20:05
We give the following constructions. For $n \ge 4$, we can consider $x^{n} - 21x^{n-2} - 12$ which is irreducible by Eisenstein's criterion and always divisible by $4$. For $n = 2, 3$, we have $x^n - 5x - 30$ which is always divisible by $2$ and never $2$ or $-2$ at an integer. Once again, it is irreducible.
10.10.2023 22:21
There are lots of possible approaches to this; the main idea is to try and force $f$ to be even. In particular, set $a_n = 3$ and $a_1 = 15$, with $a_i = 0$ for all other $i$. Notice that $f(x)$ is always even and never equal to two, but by Eisenstein with $p=3$, $f$ is irreducible.
25.11.2024 23:33