<s>[INST] 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.
 [/INST] 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.
$$
</s>