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

We can also use the symmetric polynomials.
Let $A=(1^2+1)(2^2+1) \cdots ((p-1)^2+1)(p^2+1)$. Then, $A \equiv (1^2+1)(2^2+1) \cdots ((p-1)^2+1) \mod p$, since $p^2+1\equiv 1 \mod p$.
Consider the symmetric polynomial $\displaystyle\prod_{i=1}^{\frac{p-1}2}(1+x_i)=\sum_{j=0}^{\frac{p-1}2}e_j(x)$, where $e_j$ is the $j$-th elementary symmetric polynomial.
Then $\displaystyle A\equiv(\sum_{j=0}^{\frac{p-1}2}e_j(y))^2$, where $y_i$ belongs to the set $QR:=\{1^2,\cdots,(\frac{p-1}2)^2\}$.
Now notice that $QR$ consists of roots of $x^{(p-1)/2}-1$ (over $\mathbb F_p$). So $e_j(y)$ is $(-1)^j$ times the coefficient of $x^{\frac{p-1}2-j}$ in $x^{(p-1)/2}-1$. Thus $e_0(y)=1,\,e_{(p-1)/2}(y)=(-1)^{\frac{p+1}2}$, and $e_j(y)=0$ otherwise.
Therefore $A\equiv(1+(-1)^{(p+1)/2})^2\pmod p$.
