# Prove is $n \in \mathbb{N}$ and is $p$ is prime such that $p|(n!)^2+1$ then $(p-1)/2$ is even?

Can anyone help me prove if $n \in \mathbb{N}$ and is $p$ is prime such that $p|(n!)^2+1$ then $(p-1)/2$ is even?

I'm attempting to use Fermats little theorem, so far I have only shown $p$ is odd.

I want to show that $p \equiv 1 \pmod 4$

-
Not true if $n=1$. –  Thomas Andrews May 1 '12 at 13:34
Indeed, for $n>1$ sorry –  Freeman May 1 '12 at 13:39
More generally, if $m$ is even and $p|m^2+1$ then $p\equiv 1\pmod 4$. This is just the special case where $m=n!$. –  Thomas Andrews May 1 '12 at 13:40

If $p$ divides $(n!)^2+1$, then $(n!)^2 \equiv -1 \pmod p$, so $n!$ has order $4$ in $\mathbb F_p^\times$. By Lagrange's theorem, 4 divides the order of $\mathbb F_p^\times$ which is $p-1$, hence $p \equiv 1 \pmod 4$.

-
Awesome, thanks so much for that! –  Freeman May 1 '12 at 13:51

Theorem: Let $p$ be an odd prime. Then $-1$ is a square modulo $p$ if and only if $p = 1\mod 4.$

Proof: For any $x\neq 0$ in $\mathbb{Z}_p$ call the following the bundle generated by $x$: $$B(x) = \{ x, x^{-1}, -x, -x^{-1} \}.$$

Check $B(x) = B(x^{-1}) = B(-x) = B(-x^{-1}) .$ The distinct bundles partition $\mathbb{Z}_p\setminus\{0\} .$ Since $p\neq 2$, $x\neq -x$ for all non-zero $x\in \mathbb{Z}_p,$ every package has $4$ elements unless $x= x^{-1}$ or $x=-x^{-1}.$ If $x=x^{-1}$ then $x=\pm 1$ and $B(x) =\{1,-1\}$ has $2$ elements. $x=-x^{-1}$ if and only if $x^2=-1$ and if so, $B(x) = B(-x) = \{x,-x\}$ has two elements.

If $-1$ is a square then $\mathbb{Z}_p\setminus\{0\}$ is partitioned into $2$ sets of size $2$ and the rest of size $4.$ In that case, $p-1 = 0 \mod 4.$ If $-1$ is not a square then $\mathbb{Z}_p\setminus\{0\}$ is partitioned into a set with size $2$ and the rest with size $4$, i.e $p-1=2 \mod 4.$

-

If I am not mistaken this is just a special case of the first supplement to the quadratic reciprocity law:

$p|x^2+1\Rightarrow x^2 \equiv -1 \pmod p$. This is solvable if and only if $p \equiv 1 \pmod 4$. And you have a given solution.

-
Ah thanks, that's helpful! –  Freeman May 1 '12 at 13:51