Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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}$?

share|improve this question

2 Answers 2

up vote 14 down vote accepted

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 *)
share|improve this answer
4  
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
3  
@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]

enter image description here

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

enter image description here

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)
share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.