I can intuitively understand that there are infinitely many irreducible polynomials in $\Bbb{F}_p[X]$, where $p$ is a prime number, but I'm having a hard time actually proving it. What proof strategy should I take for this?

  • 2
    $\begingroup$ Remember Euclid. $\endgroup$
    – Karanko
    Apr 6, 2015 at 5:25
  • $\begingroup$ I was thinking about his proof of infinitely many primes... $\endgroup$ Apr 6, 2015 at 5:26
  • $\begingroup$ ... and what happened? $\endgroup$
    – Karanko
    Apr 6, 2015 at 5:27
  • $\begingroup$ Suppose all primes are on this list: $p_1,...,p_r$. Then $p_1p_2\cdots p_r+1$ is also prime thus there are infinitely many $\endgroup$ Apr 6, 2015 at 5:27
  • 1
    $\begingroup$ (continued: ) Every element $\pi_i\in \{\pi_1,\cdots,\pi_r\}$ has remainder 1 after division with $\pi_1\pi_2\cdots\pi_r+1$. Thus, $\pi_1\pi_2\cdots\pi_r+1$ is also irreducible. Therefore, there are infinitely many irreducible elements in $\Bbb{F}_p[X]$. $\endgroup$ Apr 6, 2015 at 6:54

2 Answers 2


Assume that there are finitely many (monic) irreducible polynomials in $\mathbf F_{p}[X]$,$p_{1}(x), p_{2}(x), \dots, p_{n}(x)$. Consider $f(x)=p_{1}(x)p_{2}(x) \cdots p_{n}(x)+1$. Now $f(x)$ is not divisible by any irreducible, and hence is irreducible and is not in the list of irreducibles. Contradiction.

  • $\begingroup$ @AndréNicolas Why? It's known that any reducible polynomial is divisibile by an irreducible polynomial; since $f$ isn't, it must be irreducible. After all, this is a proof by contradiction, isn't it? I would make it into a direct proof, and in this case your remark would apply. $\endgroup$
    – egreg
    Apr 6, 2015 at 14:04
  • $\begingroup$ Yes, and apologies to mich95. $\endgroup$ Apr 6, 2015 at 15:54

Mimic Euclid: $\, f_{n+1}\! = 1+f_1\cdots f_n\,$ is an infinite sequence of coprimes $\,f_i.\,$ Choosing $\,g_i\,$ to be an irreducible factor of $\,f_i\,$ yields an infinite sequence of coprime (so nonassociate) irreducibles.

Alternatively, recall that the sequence of polynomials $\rm\:f_n = (x^n\!-\!1)/(x\!-\!1)\:$ is a strong divisibility sequence, i.e. $\rm\:(f_m,f_n) = f_{(m,n)}$ in $\rm\mathbb Z[x].\:$ Hence the subsequence with prime indices yields an infinite sequence of pairwise coprime polynomials. Further the linked proof shows the gcd has linear (Bezout) form $\rm\:(f_m,f_n) = f_{(m,n)}\! = g\, f_m + h\, f_n,\,$ $\rm\, g,h\in\mathbb Z[x],\:$ so said coprimality persists in every ring $\,R[x].\,$ Thus, for each prime $\rm\:q,\:$ choosing a factor of $\rm\:f_q\:$ irreducible in $R[x]$ yields infinitely many irreducible polynomials, pariwise nonassociate (being pairwise coprime).


You must log in to answer this question.

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