5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Notice the Euler criterion and that 2 is not a quadratic residue modulo $p$. $\endgroup$ – awllower Nov 21 '12 at 14:54
  • $\begingroup$ www4.ncsu.edu/~singer/437/proj32.pdf --Theorem 11.6 or mathreference.com/num-mod,qr12.html $\endgroup$ – lab bhattacharjee Nov 21 '12 at 16:16
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ +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\,$. $\endgroup$ – DonAntonio Nov 21 '12 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.