Show that $x^4+1$ is reducible in $\Bbb Z_p$ for every prime $p$-Additional Details Show that $x^4+1$ is reducible in $\Bbb Z_p$ for every prime $p$.
Though there are answers on this site for the above question,I am unable to understand why it has been used that 

Given a prime $p$ why does there always exist $a\in \Bbb Z_p$ which satisfies either $a^2=-1$ or $a^2=2$ or $a^2=-2\mod p$

Once this is proved the fact that $x^4+1$ is reducible for any prime $p$ is easy to prove.
But I am unable to understand the above fact.Can someone please explain in detail.
Attempt:
If $p=2$ then we can choose $a=1$ and hence it satisfies $a^2=1=-1\mod p$
If $p\neq 2$ then how to proceed?Please help.
 A: It is true that for each prime $p$, at least one of the congruences
$x^2\equiv-1$, $x^2\equiv2$ and $x^2\equiv-2$ is soluble. But these
cases are not "mutually exclusive", all three can be soluble, for instance
for $p=17$.
The fact that at least one is soluble comes from the theory of
quadratic residues and non-residues. The theorem one needs is that
if $p$ is an odd prime, and the congruences $x^2\equiv a\pmod p$ and
$x^2\equiv b\pmod p$ are both insoluble ($a$ and $b$ are quadratic
non-residues modulo $p$) then the congruence $x^2\equiv ab\pmod p$
is soluble ($ab$ is a quadratic residue). This boils down
to proving that the quadratic residues form a subgroup of index
two in the group $\Bbb Z_p^*$.
It is also known when each of these congruences are soluble:
$x^2\equiv-1\pmod p$ is soluble iff $p\equiv1\pmod 4$,
$x^2\equiv2\pmod p$ is soluble iff $p\equiv1$ or $7\pmod 8$,
$x^2\equiv-2\pmod p$ is soluble iff $p\equiv1$ or $3\pmod 8$.
Any introductory text on number theory will prove these.
A: Let $p$ be an odd prime.

If $a$ is an integer with $\gcd(a,p)=1$, then
$$
a^{\large{\frac{p-1}{2}}}
\equiv 
\begin{cases}
1\;(\text{mod}\;p)&\text{if $a$ is a quadratic residue, mod $p$}\\[4pt]
-1\;(\text{mod}\;p)&\text{if $a$ is a quadratic non-residue, mod $p$}\\
\end{cases}
$$
Now suppose $a,b$ are integers such that $\gcd(a,p)=1$ and $\gcd(b,p)=1$. Further suppose $a,b$ are both quadratic non-residues, mod $p$.
\begin{align*}
\text{Then}\;\;a^{\large{\frac{p-1}{2}}}&\equiv -1\;(\text{mod}\;p)\\[4pt]
b^{\large{\frac{p-1}{2}}}&\equiv -1\;(\text{mod}\;p)\\[8pt]
\text{hence}\;(ab)^{\large{\frac{p-1}{2}}}&\equiv 1\;(\text{mod}\;p)\\[4pt]
\end{align*}
It follows that for integers $a,b$ with $\gcd(a,p)=1$ and $\gcd(b,p)=1$, at least one of $a,b,ab$ is a quadratic residue, mod $p$.

Therefore at least one of $-1,2,-2$ is a square, mod $p$.

Note: The claim is that at least one is a square, not necessarily exactly one. 

As Lord Shark the Unknown points out, it could be all three (e.g., for $p=17$).

Now suppose after testing $-1,2,-2$, you've found one of them, $s$ say, which is a square, mod $p$, and you want to find an integer $r$ such that $r^2 \equiv s\;(\text{mod}\;p)$. In other words, you want to actually find a square root of $s$, mod $p$. For that task, the following link

$\qquad$http://course1.winona.edu/eerrthum/13Spring/SquareRoots.pdf

describes an algorithm to find $r$.
