# Irreducibility of a Given Polynomial

I'm starting to work with polynomial rings, and I've gotten to some problems related to irreducibility. I am trying to see if I'm approaching this problem correctly and how I can move forward with a solution. \ I want to prove that $x^2+1$ is irreducible over the integers $\mod 7.$ Take $x^2 + 1 = a(x)b(x)$ such that $a(x),b(x) \in F[x].$ I claim that $deg(a(x)) = 0 \vee deg(b(x)) = 0.$ Assume for the sake of contradiction that $deg(a(x)) = 1 \wedge deg(b(x)) = 1$ (since $deg(x^2+1) = 2$) Then $a(x) = a_1x + a_0 \wedge b(x) = b_1x + b_0$ where $a_1,a_0,b_1,b_0 \in F, a_1 \neq 0 \wedge b_1 \neq 0.$ Note that $F$ is the field of integers mod 7. Then $x^2+1 = (a_1x+a_0)(b_1x+b_0) = a_1b_1x^2 + (a_1b_0+b_1a_0)x + a_0b_0.$ This becomes somewhat of a system of equations, but I am having difficulty finding the trick to solve this to reach a contradiction. Any assistance would be greatly appreciated.

You just have to check that for any $x\in Z/7$, $x^2+1$ $\neq 0 \mod 7$. Since reducibility of degree 2 polynomial implies the existence of a root.
Compute Legendre's symbol $\left(\frac{-1}{7}\right)$.
For a polynomial $p(x) = x^2 - a \in \mathbb{Z}[x]$, $p(x)$ is irreducible over $\mathbb{Z}_p$ if $a$ is not a square modulo $p$, that is, if $\left(\frac{a}{p}\right)=-1$.
• Edited the answer. Are you familiar with Legendre's symbol? If not, you can use @Tsemo answer and try all $x \in {0,\ldots,6}$, but the way that I answered is faster when instead of $7$ you have something like nine thousand. There is also a nice formula for the Legendre's symbol $\left(\frac{-1}{p}\right)$ (google it...) – Leafar Jan 13 '16 at 0:13
• I'm not sure it's faster, as the elements of $\mathbf F_7$ can be written as $0, \pm 1,\pm 2,\pm 3$. So really there is only one square to calculate… – Bernard Jan 13 '16 at 0:17