<s>[INST] Find the remainder $R$ of $(1^2+1)(2^2+1)...(p^2+1)$ divided by $p$ 
Find the remainder $R$ of $(1^2+1)(2^2+1)...(p^2+1)$ divided by $p$, with $p$ being a prime number greater than $3$.

For $p \equiv 1 \mod 4$, there exists an integer $j$ such that $p\mid j^2+1$ (since $-1$ is a quadratic residue of $p$), therefore $R=0$. 
For $p \equiv 3 \mod 4$, how can we find $R$? Does $R$ depend on the value of $p$?
 [/INST] If $p=2$ or $p\equiv 1\pmod{4}$, then $R$ is obviously $0$ because $-1$ is a quadratic residue modulo $p$.  We assume from now on that $p\equiv 3\pmod{4}$.
Let $f(x)$ denote the polynomial $x^p-x$ over the Galois field $K=\operatorname{GF}(p)$.  Note that $f$ factorizes into
$$f(x)=\prod_{t\in K}(x-t).$$
Let $E$ be the extension $K[X]/(X^2+1)$ of $K$, which is just the Galois field $\operatorname{GF}(p^2)$.  (This is where we use the assumption that $p\equiv 3\pmod{4}$, since $X^2+1$ is irreducible over $K$.)  Write $i$ for the image of $X$ under the canonical projection $K[X]\to K[X]/(X^2+1)=E$.
Now, we have
$$R=\prod_{k=1}^p(k^2+1)=\prod_{k=1}^p(i-k)(-i-k)=\left(\prod_{k=1}^p(i-k)\right)\left(\prod_{k=1}^p(-i-k)\right).$$
By the definition of $f$, we get
$$R=f(i)f(-i)=\left(i^p-i\right)\left((-i)^p-(-i)\right)=\left(i^{p-1}-1\right)\left((-i)^{p-1}-1\right).$$
Since $\frac{p-1}{2}$ is odd, we have
$$R=\left((-1)^{\frac{p-1}{2}}-1\right)\left((-1)^{\frac{p-1}{2}}-1\right)=\big((-1)-1\big)^2=4.$$
This is an equality in $K$.  Translating this result back to $\Bbb{Z}$, we conclude that
$$R=\begin{cases}
0&\text{if}\ p=2 \vee p\equiv 1\pmod{4},\\
1&\text{if}\ p=3,\\
4&\text{if}\ p>3 \wedge p\equiv 3\pmod{4}.
\end{cases}$$
</s>