Oh man, please, it's polynomial !
I have the polynomial over . It can be easily seen that Klein's Four group is the Galois group of this polynomial.
How can I show that the corresponding polynomial
is irreducible in for every prime .
This is not true. If you take , . I think you want to prove that this polynomial is always reducible as opposed to irreducible. One way to proved is by Dedekind's theorem (again) and by an understanding of transitive subgroups of . The transitive subgroup (Klein four group) consists of an identity element and -cycle products ( ). Therefore, mod any the polynomial either splits or factors into quadradic factors. Therefore, it is always reducible.
Notice the following factorizations:
If is a square root in then we can use the factorization in  where we replace by a square root of modulo . If is a square root in then we can use the factorization in  where we replace by a square root of modulo . If neither are squares mod then it means (Legendre symbol). However, this means . Therefore, would be a square in and so we can use the factorization in .
Therefore, is always reducible for any .