Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Congruences and primes

  1. Feb 24, 2010 #1
    I came across this:

    Show that if p denotes an odd prime, then 2^((p-1)/2) = +1 (mod p).

    So basically, this is asking me to show that p|2^((p-1)/2)-1 AND p|2^((p-1)/2)+1

    But I'm stuck from there. What am I missing? Could someone help me with the proof?
  2. jcsd
  3. Feb 24, 2010 #2


    User Avatar
    Science Advisor
    Homework Helper

    Can you use Wilson's theorem?

    No, replace the AND with OR.
  4. Feb 24, 2010 #3
    The statement is called Euler's criterion for quadratic residues. The key to prove it is Fermat's theorem.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook