3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Adam Staples Mar 4 '14 at 2:04
  • $\begingroup$ math.stackexchange.com/questions/553314/… math.stackexchange.com/questions/502089/… Look similar but are a little different. $\endgroup$ – Adam Staples Mar 4 '14 at 2:08
  • $\begingroup$ The first proves more, but in particular it implies the result you are trying to prove. $\endgroup$ – André Nicolas Mar 4 '14 at 2:15
  • $\begingroup$ 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. $\endgroup$ – Adam Staples Mar 4 '14 at 2:18
  • $\begingroup$ I have posted an answer that does not mention QR explicitly. $\endgroup$ – André Nicolas Mar 4 '14 at 2:24
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – André Nicolas Mar 4 '14 at 2:30
  • $\begingroup$ My bad then. ${}{}{}$ $\endgroup$ – Pedro Tamaroff Mar 4 '14 at 2:34
  • $\begingroup$ 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! $\endgroup$ – Adam Staples Mar 4 '14 at 2:37

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.