What are all possible values of $ x \equiv a^\frac{p-1}{2} \pmod p$? Suppose p is an odd prime and a $\in$ $\mathbb{Z}$ such that  $ a \not\equiv 0 \pmod p$. What are all the values of $ x \equiv a^\frac{p-1}{2} \pmod p$ ?
This is what I got so far:
$ x^2 \equiv a^{p-1} \pmod p$
By Fermat's Little Theorem,
$ x^2 \equiv 1 \pmod p$
$ x^2 - 1 \equiv 0 \pmod p$
$ (x - 1)(x+1) \equiv 0 \pmod p$
So $\;p\mid(x-1)$ or $p\mid(x+1)$. 
 A: Going directly from your last line, you have shown that $p \mid (x+1)$ or $p \mid (x - 1)$.


*

*In the former case, you have shown that $x \equiv -1 \pmod p$.

*In the latter case, you have shown that $x \equiv 1 \pmod p$.


So these are the two candidates. It conceivably remains to show that both are actually solutions. But this is easy to check! Clearly $1^{\frac{p-1}{2}} \equiv 1 \pmod p$. When is $(-1)^{\frac{p-1}{2}} \equiv 1$? This holds exactly when $\frac{p-1}{2}$ is even (or if $p=2$). This in turn happens exactly when $p=2$ or $p \equiv 1 \pmod 4$.
So $x \equiv 1 \pmod p$ and $x \equiv -1 \pmod p$ are the possible solutions to your question. The latter only occurs when $p = 2$ or $p \equiv 1 \pmod 4$.$\spadesuit$
A: Although several correct answers have been given, I think you may find it interesting to know that this value is known as the Legendre symbol.
It is commonly denoted as
$$\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p.$$
This takes the value $0$ whenever $a \mid p$. Otherwise, it is $1$ for a quadratic residue and $-1$ for a quadratic non-residue. This is true by Euler's criterion, which is essentially what you were trying to show (and has been shown in the other answers).
A: $x^2=1 \pmod p \Rightarrow x=\pm 1\pmod p$
A: Do you know about quadratic residues ?
The values of $x$ are $1$ and $-1$.
$\frac{p-1}{2}$ values of $1$ and also $\frac{p-1}{2}$ values of $-1$.
