2
$\begingroup$

If p $\equiv$ 3 (mod 4) with p prime, prove -1 is a non-quadratic residue modulo p.

I suppose this would not be true if p $\equiv$ 1 (modulo 4). To prove something is a non-square I find to be tricky. It's difficult to see any straightforward way to do this using only the definition of congruence for example.

$\endgroup$
9
$\begingroup$

Assume $$x^2\equiv-1\pmod{p}$$

$$(x^2)^{2k+1}\equiv - 1\pmod{p}$$

$$x^{4k+2}\equiv -1\pmod{p}$$

For all $k$. Now $\exists k$ such that $4k+2=p-1$

Thus,

$$x^{p-1}\equiv-1\pmod{p}$$

Which is in clear violation of fermat's little theorem.

$\endgroup$
  • 2
    $\begingroup$ Very neat and simple. +1 $\endgroup$ – DonAntonio Apr 1 '14 at 17:53
  • $\begingroup$ @DonAntonio thank you. :) $\endgroup$ – Guy Apr 1 '14 at 17:57

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.