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.

$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|improve this question
2  
Notice the Euler criterion and that 2 is not a quadratic residue modulo $p$. –  awllower Nov 21 '12 at 14:54
    
www4.ncsu.edu/~singer/437/proj32.pdf --Theorem 11.6 or mathreference.com/num-mod,qr12.html –  lab bhattacharjee Nov 21 '12 at 16:16
add comment

2 Answers

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|improve this answer
add comment

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|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
add comment

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.