# There are infinitely many irreducible polynomials in $\Bbb{F}_p[X]$

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?

• Remember Euclid. Apr 6, 2015 at 5:25
• I was thinking about his proof of infinitely many primes... Apr 6, 2015 at 5:26
• ... and what happened? Apr 6, 2015 at 5:27
• 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 Apr 6, 2015 at 5:27
• (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]$. Apr 6, 2015 at 6:54

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.
• @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. Apr 6, 2015 at 14:04
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).