# Factorizing polynomials over fields other than $\mathbb{C}$

I'd like to take a polynomial in $\mathbb{Z}_5[x]$ of the form $ax^2+bx+c$ and factor it into irreducible polynomials.

For example:

Input...

x^2+4


Output...

(x+1)(x-1)


Note that this factorization only makes sense in $\mathbb{Z}_5[x]$

I am also interested in identifying cases which are already irreducible.

For example:

Input...

x^2+2


Output...

Polynomial is irreducible.


So, is there a way to limit Mathematica, especially functions like Solve to fields other than $\mathbb{C}$?

All of the polynomial functions, have an option Modulus which allows you to specify an integer field, like $\mathbb{Z}_5$. In particular, Factor works on your example polynomial

Factor[x^2+4, Modulus -> 5]
(* (1 + x) (4 + x) *)


Additionally, IrreduciblePolynomialQ works to determine irreducibility of $x^2+2$, as follows

IrreduciblePolynomialQ[x^2 + 2, Modulus -> 5]
(* True *)

• Damn, I saw the question and was like — "this is an easy one, I'll just spread this cream cheese on my bagel and answer it", only to see you beat me by 8 seconds when I loaded your answer. Next time, I'll reverse the order – rm -rf Apr 17 '12 at 15:02
• @R.M you have to be quick. :) – rcollyer Apr 17 '12 at 15:03
• @R.M the real challange is to add a second answer that is even better when the first one seems almost perfect :) A real artist can turn such a dead case to an epic win. – István Zachar Apr 17 '12 at 16:31
• @IstvánZachar I don't think Leonid can pull that off for this one. Although, there is room to cover other fields beyond integers, like rationals. – rcollyer Apr 17 '12 at 16:54
• Thanks, really helpful. (and so fast too!) – Harold Apr 17 '12 at 22:28

Solve with Modulus

We can use Solve with domain specification like i.e. Integers, or with e.g. integers modulo 5, then instead of specifying the domain one uses Modulus :

Solve[x^2 + 4 == 0, x, Modulus -> 5]

{{x -> 1}, {x -> 4}}

Times @@ ( x - Last @@@ %)
Expand[ %, Modulus -> 5]

(-4 + x) (-1 + x)
4 + x^2


For an integer $n$, $\mathbb{Z}_n$ is a finite ring, while for $n$ being a prime number, then it is also a field.

Factorization with Modulus or Extension

By default Mathematica factorizes polynomials over the rationals not over the complexes, if we'd like to do it over other fields we have to use :

1. Modulus for factorization over rings of integers modulo $n$
2. Extension for factorization over extended fields of rationals by algebraic numbers

In general, we have to use both options separately: if Modulus is not 0, then Extension should be None.

We can use FactorList to get a list of the factors of a polynomial, where the first element is a numerical factor, and the rest are factorizing polynomials with their exponents :

FactorList[x^2 + 4, Modulus -> 5]

{{1, 1}, {1 + x, 1}, {4 + x, 1}}


and in order to test whether we get irreducible polynomials, we can do this :

IrreduciblePolynomialQ[#, Modulus -> 5] & /@ First /@ Rest @ FactorList[x^2 + 4, Modulus -> 5]

{True, True}


Extension may have several elements,e.g. Extension->{a1, a2, a3,...,an}, then a factorized polynomial may be rewritten in terms of any rational combinations of algebraic numbers a1,a2,...,an.

We choose the following polynomial, being a minimal one having a root Sqrt[2] + Sqrt[3], to show how Extension works :

MinimalPolynomial[Sqrt[2] + Sqrt[3], x]

1 - 10 x^2 + x^4


Next, we find its roots :

Solve[1 - 10 x^2 + x^4 == 0, x]


The solutions are algebraic numbers and in order to factorize this polynomial we have to extend the field of rationals, but we do it gradually : first we factorize over the rationals, then we extend it only by rational multiples of Sqrt[2], next only by rational multiples of Sqrt[3] and finally by all rationals combinations of Sqrt[2] and Sqrt[3] :

Factor[1 - 10 x^2 + x^4, Extension -> #] & /@ {None, Sqrt[2], Sqrt[3], {Sqrt[2], Sqrt[3]}} // Column


And we check the results :

(Expand[#] === 1 - 10 x^2 + x^4) & /@ Last @ %

{True, True, True, True}


One can set e.g. Extension -> I as well, to produce in this case the same output as GaussianIntegers -> True :

Factor[x^2 + 4, Extension -> I]

(-2 I + x) (2 I + x)

• This additional detail is verily useful. I appreciate it. – Harold Apr 17 '12 at 22:28
• I added extended discussion of factorization over various fields, I believe you'll find it even more helpful than before. – Artes Apr 18 '12 at 2:30
• Tremendous. We've learned a lot today. – Harold Apr 18 '12 at 5:42