15
$\begingroup$

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

$\endgroup$

2 Answers 2

17
$\begingroup$

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 *)
$\endgroup$
12
  • 4
    $\begingroup$ 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 $\endgroup$
    – rm -rf
    Commented Apr 17, 2012 at 15:02
  • $\begingroup$ @R.M you have to be quick. :) $\endgroup$
    – rcollyer
    Commented Apr 17, 2012 at 15:03
  • 3
    $\begingroup$ @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. $\endgroup$ Commented Apr 17, 2012 at 16:31
  • $\begingroup$ @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. $\endgroup$
    – rcollyer
    Commented Apr 17, 2012 at 16:54
  • $\begingroup$ Thanks, really helpful. (and so fast too!) $\endgroup$
    – Harold
    Commented Apr 17, 2012 at 22:28
10
$\begingroup$

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)
$\endgroup$
3
  • $\begingroup$ This additional detail is verily useful. I appreciate it. $\endgroup$
    – Harold
    Commented Apr 17, 2012 at 22:28
  • $\begingroup$ I added extended discussion of factorization over various fields, I believe you'll find it even more helpful than before. $\endgroup$
    – Artes
    Commented Apr 18, 2012 at 2:30
  • $\begingroup$ Tremendous. We've learned a lot today. $\endgroup$
    – Harold
    Commented Apr 18, 2012 at 5:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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