1

Mathematica can factor easily polynomials over $\mathbb{Z}/p\mathbb{Z}$ (p prime), but I'm having a hard time trying to factor the polynomial over $\mathbb{Z}/m\mathbb{Z}$ where m is a composite number. Is there any easy way to use its factorization modulus p to obtain its factorization over m?

Thanks.

For example, $1+x+x^2+x^4$ is $(x^2+7x+10)(x^2+12x+2)$ over $\mathbb{Z}/19\mathbb{Z}$

How can I factor it over $\mathbb{Z}/779\mathbb{Z}$?

Eric Stchiike
  • 135
  • 1
    What do you mean by "its factorization" here? Such a factorization is no longer unique if $m$ has more than one prime factor. Anyway, using the Chinese remainder theorem (http://en.wikipedia.org/wiki/Chinese_remainder_theorem) you can reduce to the case that $m$ is a prime power, and then you can try to apply Hensel's lemma (http://en.wikipedia.org/wiki/Hensel's_lemma) to reduce to the case that $m$ is prime. – Qiaochu Yuan May 12 '13 at 20:13
  • I don't mind about the uniqueness of the factorization, I just want to factor it over Z/mZ – Eric Stchiike May 12 '13 at 20:15
  • 1
    An example of this phenomenon is in $\mathbb{Z}/4\mathbb{Z}$, we have $x^2=(x)(x)=(x+2)(x+2)$. – vadim123 May 12 '13 at 20:15

0 Answers0