Maths Olympiad Prep

Library / /91 of 94

Algebra Difficulty 5.7 AIME, harder Prove it United States

Problem:

Define a monic irreducible polynomial with integral coefficients to be a polynomial with leading coefficient 1 that cannot be factored, and the prime factorization of a polynomial with leading coefficient 1 as the factorization into monic irreducible polynomials. How many not necessarily distinct monic irreducible polynomials are there in the prime factorization of (x8+x4+1)(x8+x+1)\left(x^{8}+x^{4}+1\right)\left(x^{8}+x+1\right) (for instance, (x+1)2(x+1)^{2} has two prime factors)?

Solution

Solution:

x8+x4+1=(x8+2x4+1)−x4=(x4+1)2−(x2)2=(x4−x2+1)(x4+x2+1)=(x4−x2+1)(x2+x+1)(x2−x+1)x^{8}+x^{4}+1=\left(x^{8}+2 x^{4}+1\right)-x^{4}=\left(x^{4}+1\right)^{2}-\left(x^{2}\right)^{2}=\left(x^{4}-x^{2}+1\right)\left(x^{4}+x^{2}+1\right)=\left(x^{4}-x^{2}+1\right)\left(x^{2}+x+1\right)\left(x^{2}-x+1\right), and x8+x+1=(x2+x+1)(x6−x5+x3−x2+1)x^{8}+x+1=\left(x^{2}+x+1\right)\left(x^{6}-x^{5}+x^{3}-x^{2}+1\right). If an integer polynomial f(x)=anxn+⋯+a0( mod p)f(x)=a_{n} x^{n}+\cdots+a_{0}(\bmod p), where pp does not divide ana_{n}, has no zeros, then ff has no rational roots. Taking p=2p=2, we find x6−x5+x3−x2+1x^{6}-x^{5}+x^{3}-x^{2}+1 is irreducible. The prime factorization of our polynomial is thus (x4−x2+1)(x2−x+1)(x2+x+1)2(x6−x5+x3−x2+1)\left(x^{4}-x^{2}+1\right)\left(x^{2}-x+1\right)\left(x^{2}+x+1\right)^{2}\left(x^{6}-x^{5}+x^{3}-x^{2}+1\right), so the answer is 5 .

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.