MathDB
Counting polynomials that reduce to other polynomials

Source: Belarus TST 2024

July 17, 2024
algebrapolynomial

Problem Statement

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
Back to ProblemsView on AoPS