Congruences and primes

1. Feb 24, 2010

johndoe3344

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. Feb 24, 2010

CRGreathouse

Can you use Wilson's theorem?

No, replace the AND with OR.

3. Feb 24, 2010

JSuarez

The statement is called Euler's criterion for quadratic residues. The key to prove it is Fermat's theorem.