MathDB

2.2

Part of 2024 Belarus Team Selection Test

Problems(1)

Counting polynomials that reduce to other polynomials

Source: Belarus TST 2024

7/17/2024
A positive integer nn is given. Consider all polynomials P(x)=xn+an−1xn−1+…+a0P(x)=x^n+a_{n-1}x^{n-1}+\ldots+a_0, whose coefficients are nonnegative integers, not exceeding 100100. Call PP reducible if it can be factored into two non-constant polynomials with nonnegative integer coeffiecients, and irreducible otherwise. Prove that the number of irreducible polynomials is at least twice as big as the number of reducible polynomials. D. Zmiaikou
algebrapolynomial