Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
3  
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

3 Answers 3

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|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|improve this answer
1  
See also here. –  Bill Dubuque May 1 '12 at 15:37

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|improve this answer
    
Ah thanks, that's helpful! –  Freeman May 1 '12 at 13:51

Your Answer

 
discard

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.