# infinite number of irreducible polynomials in $\mathbb{Z}/2{\mathbb Z}[X]$

For $A= \mathbb{Z}/2{\mathbb Z}[X]$ ring of polynomials with coefficient in the field $\mathbb{Z}/2{\mathbb Z},$ I need to show that there are infinite number of irreducible polynomials in $A.$

How do I show that? I didn't come to any conclusion. I though of series of polynomials but since it it modulo $2$ they were not suitable.

Any direction?

(And: does any one have a link to a web where I can choose Latex symbols and see how they are written? I had one, but I lost it, and can't find it in Google)

• Hint: mimic a very, very old proof that there are infinitely many primes in some other ring.
– user29743
Jul 3, 2012 at 13:17
• Others have described a simple existential proof (+1). Another non-constructive one is to prove that finite fields of cardinality $2^n$ exist for all $n$. If you are interested in an infinite family of explicit polynomials, I refer you to an earlier answer of mine (a solution of an exercise from Lidl & Niederreiter). Jul 3, 2012 at 13:20
• Google for "latex math symbols", perhaps adding the name of the particular symbol you want help on. See also this part of the meta Math FAQ. Jul 3, 2012 at 13:28
• Someone here gave me once alink to a web where I can click the symbols/matrices and it shows as math, "cdg" something. I really liked it. Jul 3, 2012 at 13:33
• Then there's detexify. You don't even need to search a table -- just draw what you want. Jul 3, 2012 at 13:41

A variant of Euclid's proof should work fine. Assume there are only finitely many irreducible polynomials $p_1,...,p_n$ in $A$, and consider the irreducible factors of $\prod_{i=1}^n p_i + 1$.
• Besides showing that none of $p_1,...p_n$ divide the polynomial you build above, Do I need to mention or show something else? Jul 5, 2012 at 14:29
• @Jozef That's really all you need - $\prod p_i + 1$ has an irreducible factor which can't be one of the $p_i$s, so you have a contradiction. Jul 5, 2012 at 14:55
• Cocopuffs what would be different if I was asked to prove the same claim for $\mathbb Z / 3 \mathbb Z[x]$? Jul 5, 2012 at 14:58
• Doesn't $\mathbb{Z}$/2$\mathbb{Z}$ only have finite elements, since $X$ would equal $X^2$, would equal $X^3$, ...? Oct 16, 2018 at 15:04
Besides Euclid's classical method, here's another approach. 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 mod $2;\,$ indeed $\rm\:(p,q)=1\:$ for primes $\rm\:p\ne q,$ so $$\rm\,mod\ 2\!:\ \ d\:|\:f_p,f_q\ \Rightarrow\ d\:|\:g\,f_p\!+\!h\,f_q = f_{(p,q)}\! = f_1 = 1.\,$$
Thus, for each prime $\rm\:p,\:$ choosing a prime factor of $\rm\:f_p\:$ yields infinitely many prime polynomials mod $2,\,$ none associate (being pairwise coprime). Note that this argument works quite generally.