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. Fractions can be typed as 3/2, and spacing doesn't matter.
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 %1 < |a n-1 -1 + + a 0 -n | | | -1 + + | | -n %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. There is nothing to check if Re(α)≤0. 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. Otherwise, α has argument in (−π/2,π/4)∪(π/4,π/2), so the bound ∣α∣<(1+5)/2 implies that Re(α)<(1+5)/(22)<3/2.
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.
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, Amer. Math. Monthly} 109 (2002), 452--458). The final step is due to P\'olya and Szego˝.
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 reproduced verbatim; metadata (topic, difficulty) added by this project.