Prove that there are infinitely many irreducible polynomials in Z5.

[Kiwi1]

Here is my first (incorrect) attempt at a proof:

Assume that there are finitely many (say n) irreducible polynomials in \(\mathbb{Z}_5\).

Let \(a(x)=p_1(x)p_2(x)...p_i(x)...p_n(x) +1\) where \(p_i(x)\) is the i-th irreducible polynomial in \(\mathbb{Z}_5\).

a(x) is irreducible and not equal to any \(p_i(x)\) so there are at least n+1 irreducible polynomials. There are infinately many by induction.

This does not work because x(x-1)(x-2)(x-3)(x-4)=0 in Z5 so a(x)=1 and that does equal one of \(p_i(x)\).Another possibility. Perhaps I can assume a(x) to be the largest (highest degree) irreducible polynomial and the use a(x) to create a larger one. That seems unlikely because that approach does not work with prime numbers.

Or maybe I can use Fermat's little theorem to somehow create an irreducible polynomial of any degree.

Nothing I try seems to work and from the context in my book this should be easy.

 

[Deveno]

NO!

$a(x) = x(x-1)(x -2)(x - 3)(x - 4) = x(x^2 - 1)(x^2 - 4) = x(x^2 + 1)(x^2 - 1) = x(x^4 - 1) = x^5 - x$

and thus $a(x) + 1 = x^5 - x + 1$.

$a(x)$ is NOT the $0$-polynomial, $\Bbb Z_5[x]$ is NOT the same thing as polynomial functions $\Bbb Z_5 \to \Bbb Z_5$.

Put another way, $x$ is held to be transcendental over $\Bbb Z_5$ but clearly any element of $\Bbb Z_5$ is algebraic over $\Bbb Z_5$.

Your original approach is sound, but there is a certain class of polynomials you have to exclude, do you know what they are?

 

[Kiwi1]

Thanks. Usually when doing a proof by induction we start with n=1 or sometimes n=2. In this case I would need to start with n=6 or more, and to have the initial set of irreducible polys include all of the units plus at least two irreducible polynomials of degree 1 or greater. Alternatively, I could restrict a(x) to the product of monic polys, with n at least 3.

Is this what you mean by having to exclude a class of polynomials (i.e. the constants)?

Once we have the constants out of the way every time we add another irreducible polynomial to our formation of a(x) the degree of a(x) increases by at least one so I don't see how we can run into trouble.

 

[Deveno]

Units are, by definition, NOT irreducible (this is for similar reasons as 1 not being a prime number, it would, for example, prevent the concept of a unique factorization domain even EXISTING).

In a field, all the non-zero elements are units. So we have to start with the polynomials that are at least degree 1, to find ANY irreducible polynomials.

It's not much of a loss in generality to assume our polynomials are monic (although there is no *need* to do so), because if the leading coefficient of $p(x)$ is $a \neq 0$, we have that:

$\dfrac{1}{a}p(x)$

is monic, and is an associate of $p(x)$.

Note what you are essentially doing is a proof by *contradiction*, not induction:

1) you assume the list of irreducible polynomials is finite.

2) you produce a polynomial that is not divisible by any on your list of 1) (that is, it is not a multiple OR an associate of a multiple of any on your list).

3) You use the fact that the polynomial ring $F[x]$ is a UFD, for any field $F$, to derive a contradiction, which thus disproves that 1) could ever be true, so its negation must be true.

Some additional comments: for a given (known complete) list of $n$ irreducible polynomials $p_k(x)$ it is not necessarily the case that:

$p_1(x)\cdots p_n(x) + 1$ is, in fact, irreducible.

The contradiction lies in assuming the list $\{p_k(x)\}$ is COMPLETE.