$p$ an odd prime, $p \equiv 3 \pmod 8$. Show that $2^{(\frac{p-1}{2})}*(p-1)! \equiv 1 \pmod p$ $p$ an odd prime, $p \equiv 3 \pmod 8$. Show that $2^{\left(\frac{p-1}{2}\right)}\cdot(p-1)! \equiv 1 \pmod p$
From Wilson's thm: $(p-1)!= -1 \pmod p$. 
hence, need to show that $2^{\left(\frac{p-1}{2}\right)} \equiv -1 \pmod p. $
we know that $2^{p-1} \equiv 1 \pmod p.$ 
Hence:  $2^{\left(\frac{p-1}{2}\right)} \equiv \pm 1 \pmod p. $
How do I show that this must be the negative option? 
 A: All the equalities below are in the ring $\mathbb{Z}/p\mathbb{Z}$.
Note that $-1 = (p-1)! = \prod_{i=1}^{p-1}i = \prod_{i=1}^{\frac{p-1}{2}}(2i-1)\prod_{i=1}^{\frac{p-1}{2}} 2i = 2^{\frac{p-1}{2}}  \prod_{i=1}^{\frac{p-1}{2}}(2i-1)\prod_{i=1}^{\frac{p-1}{2}} i$
Now let $S_1, S_2$ be the set of respectively  all odd and even numbers in $\left \{ 1, \cdots,  \frac{p-1}{2} \right \}$ and $S_3$ be the set of all even numbers in  $\left \{ \frac{p+1}{2}, \ldots, p-1 \right \}$.
Note that $\prod_{i=1}^{\frac{p-1}{2}} i = \prod _{j \in S_1}j \prod _{k \in S_2}k = (-1)^{|S_1|} \prod _{j \in S_1}(-j)\prod _{k \in S_2}k $   $= (-1)^{|S_1|} \prod _{t \in S_3}t \prod _{k \in S_2}k  =(-1)^{|S_1|} \prod_{i=1}^{\frac{p-1}{2}}(2i)$
So  $\prod_{i=1}^{\frac{p-1}{2}}(2i-1)\prod_{i=1}^{\frac{p-1}{2}} i =  (-1)^{|S_1|}\prod_{i=1}^{\frac{p-1}{2}}(2i-1) \prod_{i=1}^{\frac{p-1}{2}} 2i = (-1)^{|S_1|} (p-1)! = (-1)^{|S_1| +1} $
Now we have $-1 =  2^{\frac{p-1}{2}} \prod_{i=1}^{\frac{p-1}{2}}(2i-1)\prod_{i=1}^{\frac{p-1}{2}} i = (-1)^{|S_1| + 1} \cdot  2^{\frac{p-1}{2}} $
i.e $\boxed{2^{\frac{p-1}{2}} = (-1)^{|S_1|}} $
Now $|S_1| = \frac{p+1}{4}$ if $\frac{p-1}{2}$ is odd and $|S_1| = \frac{p-1}{4}$ if $\frac{p-1}{2}$ is even.
So if $p \equiv 3, 5 \mod 8 $ we have $2^{\frac{p-1}{2}} = -1$.
if $p = 1,7 \mod 8$ we have $2^{\frac{p-1}{2}} = 1$. 
A: Euler's Criterion
Need an $x \in \Bbb N$ such that $2 \equiv x^2 \pmod p$. However no such $x$ exists in $\Bbb Z_p$. 
For example, in $\Bbb Z_3$, $1^2=2^2=1 \neq 2$. In $\Bbb Z_{11}$, no square number is $\equiv 2 \pmod {11}$. Leave that proof to you. If you get stuck examine $x^2-2 \equiv 0 \pmod p$.
$\Rightarrow$   $2^{(p-1)/2} \equiv -1 \pmod p$
