Maths Olympiad Prep

Library / /17 of 24

Algebra Difficulty 7.1 National Olympiad, round 2 Prove it Canada

Problem:
Let NN be the number of positive integers with 10 digits d9d8d1d0\overline{d_{9} d_{8} \cdots d_{1} d_{0}} in base 10 (where 0di90 \leq d_{i} \leq 9 for all ii and d9>0d_{9}>0) such that the polynomial
d9x9+d8x8++d1x+d0 d_{9} x^{9}+d_{8} x^{8}+\cdots+d_{1} x+d_{0}
is irreducible in Q\mathbb{Q}. Prove that NN is even.
(A polynomial is irreducible in Q\mathbb{Q} if it cannot be factored into two non-constant polynomials with rational coefficients.)

Solution

Solution:
Let f(x)=d9x9+d8x8++d1x+d0f(x)=d_{9} x^{9}+d_{8} x^{8}+\cdots+d_{1} x+d_{0}. If d0=0d_{0}=0, then f(x)f(x) is divisible by xx and thus reducible, so we may ignore all such polynomials. The remaining polynomials all have nonzero leading and constant coefficients.
For any polynomial p(x)p(x) of degree nn with nonzero leading and constant coefficients, say p(x)=anxn+an1xn1++a1x+a0p(x)=a_{n} x^{n}+a_{n-1} x^{n-1}+\cdots+a_{1} x+a_{0}, define pˉ(x)\bar{p}(x) to be the reversed polynomial a0xn+a1xn1++an1x+ana_{0} x^{n}+a_{1} x^{n-1}+\cdots+a_{n-1} x+a_{n}. Observe that pˉ(x)\bar{p}(x) also has degree nn and furthermore, pˉ(x)=xn(a0+a1(1x)++an1(1x)n1+an(1x)n)=xnp(1x)\bar{p}(x)=x^{n}\left(a_{0}+a_{1}\left(\frac{1}{x}\right)+\cdots+a_{n-1}\left(\frac{1}{x}\right)^{n-1}+a_{n}\left(\frac{1}{x}\right)^{n}\right)=x^{n} p\left(\frac{1}{x}\right).
Consider pairing each f(x)f(x) with fˉ(x)\bar{f}(x) whenever f(x)fˉ(x)f(x) \neq \bar{f}(x). If f(x)f(x) is reducible, it can be factored as f(x)=g(x)h(x)f(x)=g(x) h(x) where degg,degh1\operatorname{deg} g, \operatorname{deg} h \geq 1. Because the leading and constant coefficients of f(x)f(x) are nonzero, so are the leading and constant coefficients of g(x)g(x) and h(x)h(x). Hence gˉ(x)\bar{g}(x) and hˉ(x)\bar{h}(x) are well defined with deggˉ=degg1\operatorname{deg} \bar{g}=\operatorname{deg} g \geq 1 and deghˉ=degh1\operatorname{deg} \bar{h}=\operatorname{deg} h \geq 1. Furthermore,
fˉ(x)=x9f(1x)=x9g(1x)h(1x)=(xdeggg(1x))(xdeghh(1x))=gˉ(x)hˉ(x) \bar{f}(x)=x^{9} f\left(\frac{1}{x}\right)=x^{9} g\left(\frac{1}{x}\right) h\left(\frac{1}{x}\right)=\left(x^{\operatorname{deg} g} g\left(\frac{1}{x}\right)\right)\left(x^{\operatorname{deg} h} h\left(\frac{1}{x}\right)\right)=\bar{g}(x) \bar{h}(x)
Thus fˉ(x)=gˉ(x)hˉ(x)\bar{f}(x)=\bar{g}(x) \bar{h}(x) is a factorization of fˉ(x)\bar{f}(x) into two non-constant polynomials, so fˉ(x)\bar{f}(x) is also reducible. Therefore f(x)f(x) is irreducible if and only if fˉ(x)\bar{f}(x) is irreducible, so considering each pair, there are an even number of irreducible polynomials with f(x)fˉ(x)f(x) \neq \bar{f}(x).
Finally, note that if f(x)=fˉ(x)f(x)=\bar{f}(x), then di=d9id_{i}=d_{9-i} for each ii. In such a case, we have f(1)=(d0d9)+(d2d7)+(d4d5)+(d6d3)+(d8d1)=0f(-1)=\left(d_{0}-d_{9}\right)+\left(d_{2}-d_{7}\right)+\left(d_{4}-d_{5}\right)+\left(d_{6}-d_{3}\right)+\left(d_{8}-d_{1}\right)=0, so by the Factor Theorem, (x+1)(x+1) is a factor of f(x)f(x). Therefore these remaining polynomials are all reducible.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.