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.
 A: 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.
A: 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)
A: 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.
