# Show that if $p$ is prime and $p \equiv 3 \pmod 4$, then $\frac{p-1}{2} \not\equiv \pm1 \pmod p$

Show that if $$p$$ is prime and $$p \equiv 3 \pmod 4$$ then $$\frac{p-1}{2} \not\equiv \pm1 \pmod p$$.

Edit:

Could I say that a given is $$x^2 \equiv 1 \pmod p \iff x \equiv \pm 1 \pmod p$$ and then substitute in $$x = \frac{p-1}{2}$$ and show $$(p-1) \not\equiv 1 \mod p$$ giving me the final answer? If so how would I show this?

• I can tell we will be talking about Legendre symbols soon in this Number Theory Class (I covered them last semester in Crypto I but I do not remember how to prove this). I spent 40+ min. attempting this one. – Adam Staples Mar 4 '14 at 2:04
• math.stackexchange.com/questions/553314/… math.stackexchange.com/questions/502089/… Look similar but are a little different. – Adam Staples Mar 4 '14 at 2:08
• The first proves more, but in particular it implies the result you are trying to prove. – André Nicolas Mar 4 '14 at 2:15
• We haven't covered quadratic residues yet in this class and I vaguely have an idea of what they are from last semester so I'm not sure I still could use that for this proof. Someone can explain a proof involving it though if they like and I'll try and understand. – Adam Staples Mar 4 '14 at 2:18
• I have posted an answer that does not mention QR explicitly. – André Nicolas Mar 4 '14 at 2:24

Let $q=\frac{p-1}{2}$. Note that the numbers $q+1,q+2, \dots, 2q$ are congruent modulo $p$, in reverse order, to $-1,-2,\dots,-q$. It follows that $$(p-1)!\equiv (-1)^q(q!)^2\pmod{p}.$$ But by Wilson's Theorem, we have $$(p-1)!\equiv -1\pmod{p}.$$ It follows that $$(q!)^2\equiv (-1)^{q-1}\pmod{p}.$$ If $p=4k+3$, then $q-1=2k$, which is even. Thus $$(q!)^2\equiv 1\pmod{p}.$$ The result now follows.
• It is not, I wrote "reverse order." So for example $\frac{p+1}{2}\equiv -\frac{p-1}{2}\pmod p$. Going to the end, we have $2a=p-1\equiv -1\pmod{p}$. Do it for $p=13$. The numbers $7,8,\dots,12$ are congruent, in reverse order, to $-1,-2,\dots,-6$, or in order to $-6,-5,\dots,-1$. – André Nicolas Mar 4 '14 at 2:30
• My bad then. ${}{}{}$ – Pedro Tamaroff Mar 4 '14 at 2:34
• Okay yeah it's easy to see that 2($\frac{p-1}{2}$) $\equiv$ -1 (mod p) and then like you said working along 1 by 1 getting -1, -2, ... Then the rest follows. Alright thanks very much! – Adam Staples Mar 4 '14 at 2:37