Show a polynomial is irreducible mod 29

Question

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?

Answer 1

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.

Answer 2

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}$.

Answer 3

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$

Answer 4

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