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

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

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$

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