What do we know about the count of completely reducible polynomials modulo $p$? In other words, polynomials that factor into all linear factors and nothing of higher degree.

From this site and regarding irreducible polynomials, we have:

  1. "Counting Irreducible Polynomials"
  2. IBS's answer to "Number of monic irreducible polynomials of prime degree p over finite fields"

What we can say, if anything, about (completely or totally) reducible polynomials? More specifically, in the case where we have degree $n$ polynomials in $\mathbb{F}_p$.

  • $\begingroup$ By completely reducible you mean that the polynomial can be written as a product of linear factors? $\endgroup$ Jul 12, 2022 at 19:26
  • $\begingroup$ @SammyBlack: Yes. $\endgroup$ Jul 12, 2022 at 19:27
  • $\begingroup$ Yes, I didn't read "completely" in your question at first, and deleted my comment. I added that word to the title of your post for clarity. $\endgroup$
    – Alexander Gruber
    Jul 12, 2022 at 19:29
  • 3
    $\begingroup$ Well, how many multisets of size $n$ can you make out of $p$ elements? $\endgroup$
    – lulu
    Jul 12, 2022 at 19:30
  • 1
    $\begingroup$ I'm not saying anything complicated...sticking to monic polynomials for the moment, such a thing is determined by the list of its roots with multiplicity. That means, a multiset of size $n$. Then, of course, you have to multiply by the number of possible lead coefficients ($p-1$). $\endgroup$
    – lulu
    Jul 12, 2022 at 19:39

2 Answers 2


Completely reducible monic polynomials of degree $n$ over $\mathbb{F}_p$ are in bijective correspondence with the multiset of their roots (multiplicity counts number of linear factors for each root). Factoring in terms of the elements of $\mathbb{F}_p = \{0, 1, \dots, p-1\}$, this bijection looks like \begin{align} (x - 0)^{m_0} \cdot (x - 1)^{m_1} \cdots (x - (p-1))^{m_{p-1}} \quad&\longleftrightarrow\quad \{ 0^{m_0}, 1^{m_1}, \dots, (p-1)^{m_{p-1}} \} \\ \quad&\longleftrightarrow\quad (m_0, m_1, \dots, m_{p-1}) \end{align} where each $m_i \in \mathbb{Z}_{\geq 0}$ and the total degree is $m_0 + m_1 + \cdots + m_{p-1} = n$.

Enumerating the latter (multiset coefficient) is a well-known combinatorics exercise $$ \left(\!\!\left( \begin{matrix} p \\ n \end{matrix} \right)\!\!\right) = \binom{p+n-1}{n} $$

If you want to allow any nonzero leading coefficient, then you need to multiply the answer by $(p-1)$, since any nonzero leading coefficient is possible and determines a distinct polynomial.

  • $\begingroup$ I'm now seeing that people have been working this out with OP in the comments. Feel free to hold off and choose one of their answers if they post. Cheers. $\endgroup$ Jul 12, 2022 at 20:05

Let's start with the fact that we're working in $\mathbb{F}_p$. There are $p$ different elements, each of which we can call $a$ to create a linear factor $x-a$.

Next, we want to create a polynomial using only these linear factors. We want to create a size $n$ polynomial, and we will use exactly $n$ of our linear factors with repetition allowed.

This is precisely the "stars-and-bars" problem from combinatorics. We have $p$ different locations, which are separated using $p-1$ bars. Then we place $n$ stars into whichever locations we like, and we can place more than one in each location. For example, if we have $p=5$ locations and an $n=3$ degree polynomial, one possible solution is:

$$ | \star \star || \star |$$

You can see more on this at Wikipedia's "Stars and bars (combinatorics)" page

The result is

$$\binom{n + p - 1}{n} \text { or } \binom{n + p - 1}{p-1}$$

  • $\begingroup$ Don't forget that you need to consider the possible lead coefficients. There are $p-1$ of these, so multiply your result by $p-1$. $\endgroup$
    – lulu
    Jul 12, 2022 at 20:18
  • $\begingroup$ @lulu: Oh yeah, I forgot to mention that I was thinking about monic polynomials. Good point! $\endgroup$ Jul 12, 2022 at 20:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .