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$?

Supposing $$(x-1)(x-2)...(x-(p-1))\equiv x^{p-1}\pm1\pmod{p}$$
The left-hand side is $$(x^2-1^2)(x^2-2^2)...(x^2-({p-1\over2})^2)\pmod p$$
Replace $x^2$ by $y$; and then replace $y$ by $-1$.  The left-hand side is now a square-root of your product $\pmod p$, give or take a sign.  The right-hand side is $1\pm1$.
Can you fill in the details?
