Determine if the polynomial $P(x)=x^2-x+2 \mod p$ factors for the primes $p=5,7,11$, and $101$. Determine if the polynomial $P(x)=x^2-x+2 \mod p$ factors for the primes $p=5,7,11$, and $101$. If it does factor for a particular prime provide a factorization. If not explain why.
How would I be able to factor these polynomials? I have tried adding factors of $5x$ and $5$ but I haven't found anything.
 A: Suppose we want to factor $P(X)$ over $\mathbb{F}_p$ for an odd prime $p$. Since $P$ is monic of degree $2$, $P$ factors if and only if $P$ has a root in $\mathbb{F}_p$.
Now notice that
$$
x^2 -x  + 2 = 0 \iff 4x^2-4x+8=0 \iff (2x-1)^2 = -7
$$
in $\mathbb{F}_p$. Since $x \mapsto 2x-1$ is bijective on $\mathbb{F}_p$ for odd $p$, the polynomial $x^2-x+2$ has a root modulo $p$ if and only if $-7$ is a quadratic residue modulo $p$.
Using quadratic reciprocity we have for $p \neq 7$
$$
\left( \frac{-7}{p} \right) = \pm \left( \frac{7}{p} \right) = \left(\frac{p}{7}\right)
$$
where the $\pm$-sign is a minus iff $p \equiv 3 \mod 4$. Notice that $\left(\frac{p}{7}\right)$ is $1$ for $p=1,2,4 \mod 7$. For $p=7$ the polynomial factors as $(x+3)^2$. For $p=2$ the polynomial factors as $x(x-1)$.
In conclusion, for $p$ prime we have
$$
x^2-x+2 \mbox{ factors mod } p \iff p \equiv 0,1,2,4 \mod 7.
$$
A: Here are two suggestions as hints.
If $x^2-x+2\equiv (x-a)(x-b)\bmod p$ then $x=a$ and $x=b$ will make $x^2-x+2$ divisible by $p$. For small primes you can just try every possible value of $a$ and $b$.
You can also complete the square. Take $17$ as an example prime (because it isn't one of yours)
$$x^2-x+2\equiv x^2+16x+2 = (x+8)^2-62\equiv(x+8)^2+6 \bmod 17$$ so you need $$(x+8)^2\equiv-6\equiv 11 \bmod 17$$
So you need to tell whether $-6$ or equivalently $11$ is a quadratic residue modulo $17$. This will work more efficiently for larger primes. This is effectively recreating the familiar quadratic formula, but in the field of integers modulo $p$.
I've left out some steps so you can think about why this all works, which will help you to understand the techniques involved.
