# How to spot right $a$ value satisfying equation in $\mathbb Z/ \mathbb Z_p$ when prime $p$ is a large number

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.

-
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
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

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.

-

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.

-

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.