Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$

share|cite|improve this question
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
up vote 4 down vote accepted

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

share|cite|improve this answer
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.$

share|cite|improve this answer
See also here. – Bill Dubuque May 1 '12 at 15:37
Duplicate of this answer. Also see here for more on group-theoretic views. – Bill Dubuque May 11 at 15:46

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.

share|cite|improve this answer
Ah thanks, that's helpful! – Freeman May 1 '12 at 13:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.