Hints to prove $2^{(p−1)/2}$ is congruent to 1 (mod p) or p-1 (mod p)

Question

I'm working on this problem:

Compute the value of $2^{(p−1)/2}$ (mod p) for every prime 3 ≤ p < 20. Make a conjecture as to the possible values of $2^{(p−1)/2}$ (mod p) when p is prime and prove that your conjecture is correct.

I've computed the values for 3 ≤ p < 20 3 => 2 (mod p) 5 => 4 (mod p) 7 => 1 (mod p) 11 => 10 (mod p) 13 => 12 (mod p) 17 => 1 (mod p) 19 => 18 (mod p)

My conjecture: the result is either 1 (mod p) or p-1 (mod p)

I've having trouble figuring out how to prove my conjecture. The given equation is also very similar to Fermat's Little Theorem. I haven't yet figured out how I can simplfy/rewrite this equation to apply Fremat's Little Theorem, or how adding the /2 effects his theorem.

I'm not looking for a direct answer or anything, but some hints if I am on the right track, and if my conjecture is going in the right direction or way off.

Answer 1

Let $a=2^{(p-1)/2}$. Then $a^2=2^{p-1}\equiv1\pmod p$, by Fermat's little theorem. Can you prove that $a^2\equiv1\pmod p$ implies that $a\equiv\pm1\pmod p$?