<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] Let $p$ be a prime, with $p\equiv 3\;(\text{mod}\;4)$.

Claim:
$$\prod_{k=1}^p (1+k^2)\equiv 4\;(\text{mod}\;p)$$
Proof:
\begin{align*}
\prod_{k=1}^p (1+k^2)\;(\text{mod}\;p)
&\equiv
\prod_{k=1}^{p-1} (1+k^2)\;(\text{mod}\;p)
\\[4pt]
&\equiv
\left(\prod_{k=1}^{\frac{p-1}{2}}(1+k^2)\right)^{\!\!2}\;(\text{mod}\;p)
\\[4pt]
\end{align*}

Thus, to prove the claim, it suffices to show 
$$
\prod_{k=1}^{\frac{p-1}{2}}(1+k^2)\equiv 2\;(\text{mod}\;p)
$$
Note that
$$1+1^2,1+2^2,...,1+\left({\small{\frac{p-1}{2}}}\right)^{\!2}$$
are distinct mod $p$, and are the roots of the congruence $f(x)\equiv 0\;(\text{mod}\;p)$, where
$$f(x)=(x-1)^{\frac{p-1}{2}}-1$$
Since $p\equiv 3\;(\text{mod}\;4)$, it follows that $\frac{p-1}{2}$ is odd, hence the constant term of $f$ is $-2$.$\\[4pt]$

Note that $f$ is monic, hence by Vieta's formula, since $\frac{p-1}{2}$ is odd, and the constant term of $f$ is $-2$, the product in $Z_p$ of the roots of $f$ is $2$, so we get
$$
\prod_{k=1}^{\frac{p-1}{2}}(1+k^2)\equiv 2\;(\text{mod}\;p)
$$
which proves the claim.

Thus, if $p$ is prime, with $p\equiv 3\;(\text{mod}\;4)$, we get $R\equiv 2^2\;(\text{mod}\;p)$, hence 
$$
\begin{cases}
R=4,\;\text{if}\;p > 3\\[4pt]
R=1,\;\text{if}\;p = 3\\
\end{cases}
$$
</s>