How many solutions to $a^{(p-1)/2} \equiv 1 (p)$

Question

I am currently stuck on why this congruence has $(p-1)/2$ solutions. I know Fermat's little theorem, and how one can deduce that $a^{p-1} \equiv 1 (p)$ has at most $p-1$ solutions. I am not sure about this one above though. Thanks.

Answer 1

Since $\mathbb{Z}/p\mathbb{Z}$ is a field, the polynom $X^{\frac{p-1}{2}}-1\in\mathbb{Z}/p\mathbb{Z}[X]$ has at most $\frac{p-1}{2}$ distinct solutions. However, if $a\in(\mathbb{Z}/p\mathbb{Z})^*$ is a square in $\mathbb{Z}/p\mathbb{Z}$, there exists $b\in(\mathbb{Z}/p\mathbb{Z})^*$ such that $a=b^2$ and $a^{\frac{p-1}{2}}=b^{p-1}=1$ by Fermat's theorem, thus all the squares except $0$ are solutions. Moreover, let $\varphi:(\mathbb{Z}/p\mathbb{Z})^*\longrightarrow (\mathbb{Z}/p\mathbb{Z})^*$ defined by $\varphi(a)=a^2$, we have $$ \varphi(a)=\varphi(b)\iff a^2-b^2=0\iff (a+b)(a-b)=0\iff a=\pm b $$ because $\mathbb{Z}/p\mathbb{Z}$ is a field. However, if $b\neq 0$, $b\neq -b$ thus the set of squares in $(\mathbb{Z}/p\mathbb{Z})^*$ (which is $\mathrm{Im}\,\varphi$) has exactly $\frac{|(\mathbb{Z}/p\mathbb{Z})^*|}{2}=\frac{p-1}{2}$ elements and the roots of $X^{\frac{p-1}{2}}-1$ are exactly the squares of $(\mathbb{Z}/p\mathbb{Z})^*$, thus there are $\frac{p-1}{2}$ solutions.

Answer 2

The only square roots of $1$ in $\mathbb{Z}_p$ are $\pm 1$ (this is because the polynomial $x^2-1$ can have at most 2 roots in this field). Any $a\ne 0$ has, by Fermat's little theorem, $a^{(p-1)/2}$ a square root of $1$, so $a^{(p-1)/2} = \pm 1$. The result will follow if we can show there is an element $b$ so that $b^{(p-1)/2} = -1$. If this is the case, then the map $a\mapsto ba$ will be a bijection between the values $a$ with $a^{(p-1)/2} = 1$ and those with $a^{(p-1)/2} = -1$. In particular, those in the latter group are exactly half of the $p-1$ total, giving $p-1$ solutions.

To get such a $b$, consider cases. If $p \cong 3$ mod 4, take $b=-1$. If $p \cong 1$ mod 4, then $-1$ is a quadratic residue mod $p$, and we can take $b$ so that $b^2 = -1$.

Answer 3

If you have studied group theory then a simple proof follows from noting that the non-zero elements of $\mathbb{Z}_p$ form a cyclic group.

Let $g$ be a generator and then a power of $g$, $a=g^i$, will satisfy $a^{(p-1)/2} \equiv 1 (p)$ if and only if $i$ is even.