Irreducible Polynomials Junior

Given a prime number $p$, consider the set Z_p = \{0, 1, \ldots, p-1\}—the field of remainders modulo $p$. In this field, both multiplication and addition are performed modulo $p$.

Now, consider the set of monic polynomials over this field of the form

where $n$ is the degree of the polynomial, $x$ is the variable, and a_i \in Z_p are coefficients.

For example, the polynomial x^2 + x + 1 in the field Z_2 is irreducible. A monic polynomial is called irreducible if it cannot be represented as f(x) = p(x) \cdot q(x), where $p(x)$ and $q(x)$ are polynomials of lower degree than $f(x)$. Notably, this is the only irreducible polynomial of degree two in Z_2.

Your task is to compute the number of irreducible monic polynomials of degree $n$ in the field Z_p.