Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need to factorize $f=8x^3+x^2+2x+6 \in \mathbb Z_{13}[x]$. I figure I can divide $f$ by $(x-a)$ and then determine for which $a$ value the reminder is equal to $0$.

So the resulting quotient is $8x^2+(8a+1)x+(3+8a)$ and the reminder is $6+a(3+8a)$. As previously said I have to find a suitable $a$ value solution to $$\begin{align} 6+a(3+8a)\equiv_{13}0 \Leftrightarrow a(3+8a)\equiv_{13}7\end{align}$$

at this point I have to manually substitute the $a$ to $0,1,2,\,...$ and verify for every value which among them satisfies the equation. My question is for a small number like $13$ it is acceptable to run tests and see, but what if instead of $13$ there was $31$, is there any way that lets me spot that value without embarking in a pretty time consuming quest?

Edit: I'm not in the math field, but I have to take the exam, maybe this question is going beyond the contents of my class, so I was wondering if there is any resonably simple answer to that.

share|improve this question
    
You want a general method for all polynomials ? or just this polynomial in different fields –  Amr Nov 25 '12 at 12:18
    
Preferably a general one or using this particular example a way to generalize to other polynomials in different fields, if possible. –  haunted85 Nov 25 '12 at 12:21
2  
I would be a little careful with writing $\mathbb Z_p$. Some take it to mean the ring of $p$-adic integers. Alternative notations for integers mod $p$ are $\mathbb Z/p\mathbb Z = \mathbb Z/(p)$ (quotienting out by the ideal $p\mathbb Z=(p)$). –  kahen Nov 25 '12 at 12:44
    
Thank you @kahen I wasn't aware of that. My textbook uses freely this notation and so did I. –  haunted85 Nov 25 '12 at 12:48
add comment

3 Answers

up vote 0 down vote accepted

Instead of dividing $f(x)$ with $x-a$ and then trying to find $a$ s.t. the remainder is zero sometimes is easier to first find $a$ s.t. $f(a)\equiv0$ and then divide with $x-a$.
Of course this method to factorize $f(x)$ is sufficient only if $\deg f\leq3.$

For this particular example:
write $f(x)\equiv_{13}-5x^3+x^2+2x+6$. Then calculate $f(0),f(\pm1),f(\pm2),\ldots,f(\pm6)$ until you find a zero. Here $f(2)\equiv_{13}0$.
Next we divide $f(x)$ with $x-2$ in $\mathbb Z_{13}[x]$. We get $f(x)\equiv_{13}(x-2)(-5x^2+4x-3)$.
Then we repeat for $g(x)=-5x^2+4x-3$. Since $g(a)\not \equiv_{13} 0, \ \forall a \in \mathbb Z_{13} \Rightarrow g(x)$ is irreducible in $\mathbb Z_{13}[x]$.

Also check this, this and this.

share|improve this answer
add comment

You want to find a solution to $a x^2 + bx + c =_p 0$ for a prime $p$ and integers $a, b, $ and $c$, or show no solution exists. My first inclination is to reduce this to quadratic residues.

If $a =_p 0$, this is just linear, so assume $a \ne_p 0$. Multiplying by $1/a$, this becomes $x^2+Bx+C =_p 0$. Completing the square, this becomes $(x+B/2)^2 =_p -C-(B/2)^2$. If $-C-(B/2)^2$ is a quadratic residue (this can be done in time $O(\ln p)$), then you can find $x$. If not, there is no solution.

share|improve this answer
add comment

You mean something like Berlekamp's algorithm?

Also, Chapter 4 of the Lidl - Niederreiter book (Introduction to finite fields and their applications) is dedicated on this subject -- if you can access it through a library or so.

(posting as an answer, since I cannot add comments yet)

share|improve this answer
add comment

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.