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

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

share|cite|improve this question
Notice the Euler criterion and that 2 is not a quadratic residue modulo $p$. – awllower Nov 21 '12 at 14:54 --Theorem 11.6 or,qr12.html – lab bhattacharjee Nov 21 '12 at 16:16

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

share|cite|improve this answer

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$

share|cite|improve this answer
+1 Very nice and to the point. It could perhaps be added that $\,2\,$ is a square modulo a prime $\,p\,$ iff $\,p=\pm 1\pmod 8\,$. – DonAntonio Nov 21 '12 at 17:09

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.