Let P(x) be a polynomial whose coefficients are all either 0 or 1. Suppose that P(x) can be written as a product of two nonconstant polynomials with integer coefficients. Does it follow that P(2) is a composite integer?
A number or a short expression. Spacing and $ signs are ignored.
Solution
Yes, it follows that P(2) is a composite integer. (Note: 1 is neither prime nor composite.)
Write P(x)=a0+a1x+⋯+anxn with ai∈{0,1} and an=1. Let α be an arbitrary root of P. Since P(α)=0, α cannot be a positive real number. %In addition, if α=0 then %\begin{align*}
%1 &< |a_{n-1} \alpha^{-1} + \cdots + a_0 \alpha^{-n}| \\
%&\leq |\alpha|^{-1} + \cdots + |\alpha|^{-n}
%\end{align*} %and so ∣α∣<2. % In addition, if α=0 then ∣1+an−1α−1∣=∣an−2α−2+⋯+a0α−n∣≤∣α∣−2+⋯+∣α∣−n. If α=0 and Re(α)≥0, then Re(1+an−1α−1)≥1 and 1≤∣α∣−2+⋯+∣α∣−n<1−∣α∣−1∣α∣−2; this yields ∣α∣<(1+5)/2.
By the same token, if α=0 then ∣1+an−1α−1+an−2α−2∣≤∣α∣−3+⋯+∣α∣−n. We deduce from this that Re(α)≤3/2 as follows. \begin{itemize} \item There is nothing to check if Re(α)≤0. \item If the argument of α belongs to [−π/4,π/4], then Re(α−1),Re(α−2)≥0, so 1≤∣α∣−3+⋯+∣α∣−n<1−∣α∣−1∣α∣−3. Hence ∣α∣−1 is greater than the unique positive root of x3+x−1, which is greater than 2/3. \item Otherwise, α has argument in (−π/2,π/4)∪(π/4,π/2), so the bound ∣α∣<(1+5)/2 implies that Re(α)<(1+5)/(22)<3/2. \end{itemize}
By hypothesis, there exists a factorization P(x)=Q(x)R(x) into two nonconstant integer polynomials, which we may assume are monic. Q(x+3/2) is a product of polynomials, each of the form x−α where α is a real root of P or of the form (x+23−α)(x+23−α)=x2+2Re(23−α)x+23−α2 where α is a nonreal root of P. It follows that Q(x+3/2) has positive coefficients; comparing its values at x=1/2 and x=−1/2 yields Q(2)>Q(1). We cannot have Q(1)≤0, as otherwise the intermediate value theorem would imply that Q has a real root in [1,∞); hence Q(1)≥1 and so Q(2)≥2. Similarly R(2)≥2, so P(2)=Q(2)R(2) is composite.
\textbf{Remark.} A theorem of Brillhart, Filaseta, and Odlyzko from 1981 states that if a prime p is written as ∑iaibi in any base b≥2, the polynomial ∑iaixi is irreducible. (The case b=10 is an older result of Cohn.) The solution given above is taken from: Ram Murty, Prime numbers and irreducible polynomials, \textit{Amer. Math. Monthly} \textbf{109} (2002), 452--458). The final step is due to P\'olya and Szeg\H{o}.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: Omni-MATH,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.