A hint on why if $c$ is not a square in $\mathbf{F}_p$, then $c^{(p - 1)/2} \equiv -1 \mod p$

Question

Let $\mathbf{F}_p$ be a finite field and let $c \in (\mathbf{Z}/p)^\times$. If $x^2 = c$ does not have a solution in $\mathbf{F}_p$, then $c^\frac{p - 1}{2} \equiv -1 \mod p$.

I will try to prove the contrapositive: Suppose that $c^\frac{p - 1}{2} \not\equiv -1 \mod p$. We show that $x^2 = c$ has a solution in $\mathbf{F}_p$. By Fermat's Theorem, $c^{p - 1} \equiv 1 \mod p$. Then $c^{p - 1} - 1 \equiv 0 \mod p$. Then $(c^\frac{p - 1}{2} + 1)(c^\frac{p - 1}{2} - 1) \equiv 0 \mod p$. This implies that either $c^\frac{p - 1}{2} \equiv -1 \mod p$ or $c^\frac{p - 1}{2} \equiv 1 \mod p$.

Hence it must be that $c^\frac{p - 1}{2} \equiv 1 \mod p$.

I'm not sure how to derive an $a \in \mathbf{F}_p$ such that $a^2 = c$.

Answer 1

We assume $p$ is odd, and use an argument that yields additional information.

There are two possibilities, $p$ is of the form $4k-1$, and $p$ is of the form $4k+1$.

Let $p$ be of the form $4k-1$. If $c^{(p-1)/2}\equiv 1\pmod{p}$, then $c^{(p+1)/2}\equiv c\pmod{p}$. But $\frac{p+1}{2}=2k$, and therefore $$(c^k)^2\equiv c\pmod{p}.$$

To complete things, we show that if $p$ is of the form $4k+1$, then the congruence $x^2\equiv -1\pmod{p}$ has a solution. The argument goes back at least to Dirichlet.

Suppose that $x^2\equiv -1\pmod{p}$ has no solution. Consider the numbers $1,2,\dots,p-1$. For any $a$ in this collection, there is a $b$ such that $ab\equiv -1\pmod{p}$. Pair numbers $a$ and $b$ if $ab\equiv -1\pmod{p}$. Since the congruence $x^2\equiv -1\pmod{p}$ has no solution, no number is paired with itself. The product of all the pairs is $(p-1)!$, and it is also congruent to $(-1)^{(p-1)/2}$ modulo $p$. Since $\frac{p-1}{2}$ is even, it follows that $(p-1)!\equiv 1\pmod{p}$, which contradicts Wilson's Theorem.

Answer 2

Hints (fill in the missing details):

• If $c=x^2$, $x\neq0$, then $c^{(p-1)/2}=x^{p-1}=1$ by Little Fermat.
• If $x^2=y^2$, $x\neq0$, then $(x-y)(x+y)=0$, so $y=\pm x$. Therefore there are $(p-1)/2$ distinct non-zero squares $q$, and all those satisfy $q^{(p-1)/2}=1$.
• Because the equation $x^{(p-1)/2}=1$ is of degree $(p-1)/2$, it can have at most $(p-1)/2$ solutions. And we have found all of them.
• Put this together with what you have to conclude that if $c$ is a non-square, then $c^{(p-1)/2}=-1$.