Primality and Factorization, Irreducibility and the Matrix Method

Irreducible Polynomial over a UFD

Let R be a ufd, let w(x) be a monic polynomial over R, and let S be R[x] mod w(x). If w is the product of two lesser polynomials then S has a zero divisor. Conversely, let g*h = 0 in S. Thus g(x)*h(x) is w(x) times some other polynomial. Since R[x] is a ufd, factor everything into irreducible polynomials. Some piece of w divides g or h, hence w is reducible. Thus w is irreducible iff S has no zero divisors.

Since S is a free R module, multiplication is defined by the image of the basis elements 1, x, x2, x3, etc. Multiplication by x, for instance, maps this basis to x, x2, x3, and so on up to xn-w(x). Write a matrix M that defines multiplication for all of S. Now S has a zero divisor iff an input vector times M yields the zero vector. Therefore S has no zero divisors, and w is irreducible, iff M is nonsingular. This can often be computed directly, using gaussian elimination. Embed R in its fraction field if necessary.

If R is already a field, such as the integers mod p, then we're good to go. The polynomial w defines a finite field extension of dimension n iff the corresponding matrix has a nonzero determinant.

Two Quotient Rings

Let R be an integral domain, and let I and J be ideals, such that I+J is all of R. Let Q1 and Q2 be the two quotient rings. Assume these quotient rings are ufds, so that the above theorem applies. Let Q3 be R mod IJ. By the chinese remainder theorem, Q3 is isomorphic to the direct product of Q1 and Q2. So let's work within this direct product.

Let w be a monic polynomial of degree n, with components w1 and w2. Since 1 projects to 1, both w1 and w2 are monic of degree n. These components are irreducible iff the corresponding matrices are nonsingular, iff both determinants are nonzero. This happens iff the matrix of w, over R, has a determinant that does not belong to I or J.

In some cases this is easily calculated. For instance, let R be Z, and let I be the multiples of 3, and let J be the multiples of 5. All calculations will now be taken in Q3, or the integers mod 15. Given a monic polynomial w, which may have thousands of terms, build the matrix M and take its determinant. Then check for divisibility by 3 or 5. Both w1 and w2 are irreducible iff det(M) is a unit mod 15.

Mod p2

Let w be a monic polynomial whose coefficients are integers mod p2. If w is the product of two lesser polynomials then the same is true mod p. Turn this around, and irreducibility mod p pulls back to irreducibility mod p2. Since units mod p2 map onto units mod p, a unit determinant mod p2 implies a unit determinant mod p, implies irreducibility. This generalizes to higher powers of p.

Put this all together and let w be a monic polynomial whose coefficients are integers mod d. now w is irreducible mod each prime power if the determinant of the corresponding matrix is a unit mod d.