Polynomial , where each
is divisible by some number
, is irreducible in
when
does not divide
.
If A is not irreducible then there are some and
such as
.
But that means that , which means that
XOR
(since
does not divide
).
Let’s assume that . Now let’s take a map
(I believe this method is called homomorphism-reduction).
, but
, where
.
That is possible only when is constant and
. Which means that
is irreducible.
Note: here denotes
where
is a homomorphism
.