Представьте многочлен P(x)=x^100+x^20+1 в виде произведения четырёх многочленов ненулевой степени с целыми коэффициентами.
Эта задача была на молдавском отборе 2004 года к юниорской Балканской олимпиаде. Для начала заметим, что x^5+x+1=(x^2+x+1)(x^3-x^2+1).
Следовательно,
P(x)=x^100+x^20+1=(x^40+x^20+1)(x^60-x^40+1).
Теперь заметим, что x^4+x^2+1=(x^2+x+1)(x^2-x+1) и применим эту формулу два раза:
P(x)= (x^40+x^20+1)(x^60-x^40+1)=(x^20-x^10+1)(x^20+x^10+1)(x^60-x^40+1);
P(x)=(x^20-x^10+1)(x^10-x^5+1)(x^10+x^5+1)(x^60-x^40+1).
Представление мы получили, но у читателей, возможно, возник вопрос, как мы замечали такие равенства.
Со вторым замечанием попроще. Надо лишь применить формулу разности квадратов:
x^4+x^2+1=x^4+2x^2+1-x^2=(x^2+1)^2-x^2=(x^2-x+1)(x^2+x+1).
С первым замечание посложнее. Я предлагаю умножить на (x-1):
(x^5+x+1)(x-1)=x^6-x^5+x^2-1=(x^6-1)-x^2(x^3-1)=(x^3-1)(x^3+1)-x^2(x^3-1)=
=(x^3-x^2+1)(x^3-1)=(x^3-x^2+1)(x^2+x+1)(x-1).
"Откинув" скобку (x-1), на которую мы т