Find the remainder $R$ of $(1^2+1)(2^2+1)...(p^2+1)$ divided by $p$

Question

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

Answer 1

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

Answer 2

If $ p $ is not $ 3 $ modulo $ 4 $ the given expression is trivially $ 0 $, so assume $ p \equiv 3 \pmod{4} $.

Consider the polynomial

$$ P(x) = \prod_k (x + k) $$

where the product is taken over all $ k $ which are quadratic residues mod $ p $ (excluding $ 0 $). First, observe that if $ r $ is a quadratic residue mod $ p $, then

$$ P(r) = \prod_k (r + k) = r^{(p-1)/2} \prod_k (1 + k r^{-1}) = \prod_k (1 + k) = P(1) = c $$

In addition, it follows by pairing each non-identity quadratic residue with its inverse that $ P(0) = 1 $. The only polynomial mod $ p $ of degree $ \leq (p-1)/2 $ which satisfies these conditions is $ (c-1) x^{(p-1)/2} + 1 $ (it's easy to check that it has the required values, and uniqueness is easy to see.) Since $ P $ has leading coefficient $ 1 $, it follows $ c = 2 $, and so $ P(1) = 2 $. The expression given in the question is $ P(1)^2 $, which is therefore always equal to $ 4 $ mod $ p $.

Answer 3

With this script in MATHEMATICA you can check a lot

n=10000 primes = Select[Range[n], PrimeQ[#] && NextPrime[#] == 2 + # &] p[n_] := Product[1 + k^2, {k, 1, n}] For [j = 1, j <= Length[primes], j++, Print[primes[[j]], " ", Mod[p[primes[[j]]], primes[[j]]]]]

What to say about this pattern for the first bunch ?

$$ \{1,0,4,0,0,0,4,4,0,4,0,0,4,4,0,4,4,0,0,4,4,4,4,0,0,0,4,0,0,4,0,0,4,0,0,4,4,0,0,4,4,0,0,0,0,4,4,4,0,4,4,4,4,0,0,4,4,0,4,0,0,4,0,4,4,0,0,0, 4,0,4,0,0,4,0,4,4,0,0,0,0,4,4,4,4,0,4,0,4,4,0,0,4,4,4,0,0,4,4,0,4,0,0,0,4,0,4,4,0,0,0,0,4,4,0,0,0,0,4,0,0,0,4,4,4,4,0,0,4,4,4,0,0,0,0,4 ,4,4,0,0,0,4,4,0,4,0,0,4,4,0,4,0,4,0,0,0,4,4,4,0,4,4,4,4,4,4,0,0,4,4,4,0,0,0,0,0,4,4,4,4,4,0,0,0,4,4,0,0,0,4,4,0,4,0,0,4,4,0,0,0,0,4,4, 0,0,\cdots \} $$

Answer 4

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