$p$ an odd prime, $p \equiv 3 \pmod 8$. Show that $2^{(\frac{p-1}{2})}*(p-1)! \equiv 1 \pmod p$

Question

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

Answer 1

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

Answer 2

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$