What are all possible values of $ x \equiv a^\frac{p-1}{2} \pmod p$?

Question

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)$.

Answer 1

Going directly from your last line, you have shown that $p \mid (x+1)$ or $p \mid (x - 1)$.

1. In the former case, you have shown that $x \equiv -1 \pmod p$.
2. 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$

Answer 2

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).

Answer 3

$x^2=1 \pmod p \Rightarrow x=\pm 1\pmod p$

Answer 4

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$.