# What are all the 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$

$\;p\mid(x-1)\;\; or\;\; p\mid(x+1) \;$

-
So $x\equiv 1\pmod{p}$ or $x\equiv -1\pmod{p}$. You may be expected to explain why both are achievable for any odd prime $p$. – André Nicolas Feb 10 '14 at 19:42
what do you mean? – sarah Feb 10 '14 at 19:46
You had basically proved (except for not quite finishing) that $x\equiv \pm 1\pmod{p}$. It is obvious that $1$ is possible for any $p$ (let $a=1$). To show that there is an $a$ such that $a^{(p-1)/2}\equiv -1\pmod{p}$, let $a$ be any quadratic non-residue of $p$, – André Nicolas Feb 10 '14 at 19:51
Can you explain what is a quadratic non-residue of p? – sarah Feb 10 '14 at 20:09
It is a number $b$ not divisible by $p$ such that there is no $y$ such that $y^2\equiv b\pmod{p}$. Informally, it is a non-square modulo $p$. – André Nicolas Feb 10 '14 at 20:15

$x^2=1 \pmod p \Rightarrow x=\pm 1\pmod p$
The values of $x$ are $1$ and $-1$.
$\frac{p-1}{2}$ values of $1$ and also $\frac{p-1}{2}$ values of $-1$.