Show a polynomial is irreducible mod 29 Is there an easy way to see that the polynomial $x^2 + 3x + 10$ is irreducible modulo 29 without having to go through each element 0,1,..,28 and check for roots?
 A: Probably not. But I can suggest a harder way. The congruence $x^2+3x+10\equiv 0$ can be rewritten as $4x^2+12x+40\equiv 0$, and then as $(2x+3)^2+31\equiv 0$ and then as $(2x+3)^2 \equiv -2$. So the issue is whether $-2$ is a quadratic residue of $29$. Note that $-1$ is a QR of $29$. But $2$ is an NR of $29$, since $29$ is of the form $8k+5$. So $-2$ is an NR of $29$, no solutions.
A: One way to show it isn't a root is to complete the square.
$$
x^2+3x+10
\equiv x^2 -26x + 155 
= (x-13)^2 -14 \pmod{29}
$$
Now, to show that there is no root is equivalent to showing that $14$ is not a quadratic residue mod 29.  Using quadratic reciprocity and the Lagrange symbol, we compute
$$
\binom{14}{29} = \binom{2}{29}\binom{7}{29}
= - \binom{29}{7} = -\binom{1}{7} = -1
$$
Thus, there is no solution to $x^2 = 14\pmod{29}$, and therefore no solution to $(x-13)^2-14 = 0 \pmod{29}$.
A: Note that $$x^2+3x+10\equiv x^2+32x+10 = (x+16)^2-246$$ So the real question is whether $246\equiv 14\equiv 72 \bmod 29$ is a square modulo $29$ i.e. whether $6^2\times 2$ is a square modulo $29$, i.e. whether $2$ is a square. But $2$ is a square modulo a prime $p$ only if $p\equiv \pm 1 \bmod 8$
A: One doesn't need quadratic reciprocity, only the simple idea behind Euler's Criterion
$ {\rm mod}\ 29\!:\ 0 \equiv 4f(x) \equiv {(2x\!+\!3)^2}\!+31\,\Rightarrow \color{#0a0}{(2x\!+\!3)^2\equiv -2}.\ $ But $\,\color{#0a0}{-2}\,$ is not a square by
$\qquad \color{#0a0}{a^2 \equiv  -2}\!\!\overset{\large\ \ (\,\ )^{14}}\Rightarrow\!  a^{28} \equiv  2^{14} \equiv  \dfrac{(2^5)^3}{2} \equiv  \dfrac{3^3}{2}\equiv \dfrac{-2}{2} \equiv  \color{#c00}{-1},\,$ contra little Fermat
