# Prove that $a^{(p-1)/2} \equiv 1$ (mod p) and $a^{(p-1)/2} \equiv -1 \pmod p$

I've stumbled upon this congruence very similar to Fermat's Little Theorem, but I can't seem to wrap my head around how to solve it. It goes like this:

i) Suppose $$p$$ is prime, $$(a,p)=1$$ and the congruence $$x^2 \equiv a \pmod p$$ has a solution $$x$$. Prove that $$a^{(p-1)/2}\equiv 1 \pmod p$$.

And the same question but with an additional condition:

ii) Suppose $$p$$ is prime, $$p \equiv 3 \pmod 4$$, $$(a,p) = 1$$ and the congruence $$x^2 \equiv a \pmod p$$ does not have a solution $$x$$. Prove that $$a^{(p-1)/2}\equiv -1 \pmod p$$.

For i: Since $$x^2 \equiv a \pmod p$$ has a solution, we know that $$p \mid x^2 - a$$, hence $$kp=x^2-a$$ for some integer $$k$$, or $$a = x^2-kp$$. Now this doesn't really help me much!

For ii: Similarly stumped.

• As noted in one of the answers, the condition $p \equiv 3 \pmod{4}$ in (ii) is superfluous. – Andreas Caranti Sep 23 '13 at 7:53

Hints:

(i) If $x^2 \equiv a \pmod p$ then what is $a^{\frac{p-1}{2}}$ as a power of $x$? Do this and apply Fermat's little theorem.

(ii) Write $x=a^{\frac{p-1}{2}}$. Fermat's little theorem gives you $x^2 \equiv 1 \pmod p$. Now use the rest of the information you've been given.

For the first part, note that $x^{p-1}\equiv 1$ by Fermat's little theorem. Then assuming that $p$ is not $2$ (deal with that case separetly), we have $1\equiv (x^2)^{(p-1)/2}\equiv a^{(p-1)/2}$.

For the second part, let $\alpha$ be a primitive element (this means that there is an element $\alpha$ in $\{1,...,p-1\}$ such that $\alpha$ has order exactly $p-1$ (this means that $\alpha^i$ will range through $\mathbb{Z}_p^\times$ as we let $i=1,2,..,p-1$).

Then, since $a$ is not a square, we have that $a=\alpha^{2c+1}$, so $$a^{(p-1)/2}\equiv (\alpha^{2c+1})^{(p-1)/2}\equiv \alpha^{c(p-1)}\alpha^{(p-1)/2}\equiv \alpha^{(p-1)/2}$$Now note that $\alpha^{(p-1)/2}$ is a root of $x^2-1$. Also note that $1$ and $-1$ are also roots. Note that we cannot have three roots (the degree of $x^2-1$ is $2$ and over a field, the degree bounds the number of roots), so we have that $\alpha^{(p-1)/2}$ is either $1$ or $-1$, but it cannot be $1$ since the order of $\alpha$ is $p-1$, hence it is $-1$, and we are done. I just realized that I did not use the fact that $p\equiv 3\pmod{4}$ (all i used was $p\neq 2$), so I guess the conditions can be weakened.

For the first one, one just has to compute: $a^{(p-1)/2} = x^{2(p-1)/2} = x^{p-1} = 1 \mod p$.

For the second one, let $p = 4k + 3$. $a^{(p-1)/2}$ is a root of $X^2 - 1$ (as above) which has only two solutions: $1$ and $-1$. If $a^{(p-1)/2} = 1\mod p$, $a^{(p-1)/2}a = a \mod p$, and $a^{(p-1)/2}a = a^{(p+1)/2} = a^{2(k+1)} = {(a^{k+1})}^2$, hence $x^2 = a$ has a solution, which is a contradiction. Hence $a^{(p-1)/2} = -1\mod p$.

This is an important theorem due to Leonhard Euler reworded in a different essence I think and it is usually proved at the beginning of an introduction to quadratic residues.

First you need to know that in a complete residue system modulo $p$, there are exactly $\frac{p-1}{2}$ quadratic residues and $\frac{p-1}{2}$ non-residues and the quadratic residues are $1^2,2^2, \cdots, (\frac{p-1}{2})^2$. This could be checked as an easy exercise. If you needed further help with this let me know.

By using Fermat's little theorem we know that $a^{p-1} \equiv 1 \pmod{p}$.

Now I'll give you a sketch of proof for Euler's criterion, you can work out the details on your own. You can factor $a^{p-1} -1$ as $$a^{p-1}-1=(a^{(p-1)/2}-1)(a^{(p-1)/2}+1)$$

$$\implies 0 \equiv a^{p-1}-1\equiv (a^{(p-1)/2}-1)(a^{(p-1)/2}+1) \pmod{p}$$

But since $p$ is a prime number, then $a^{(p-1)/2}-1 \equiv 0 \pmod{p}$ or $a^{(p-1)/2}+1 \equiv 0 \pmod{p}$

You can check that $1^2, 2^2, \cdots, (\frac{p-1}{2})^2$ satisfy $x^{(p-1)/2} \equiv 1 \pmod{p}$. Now if you work out the details now which is easy I think it's obvious that $a$ is a non-residue if and only if $a^{(p-1)/2} \equiv -1 \pmod{p}$.

If you're familiar with Legendre's symbol you can state this theorem this way as well:

$$\left(\frac{a}{p}\right) \equiv a^{(p-1)/2}\ \pmod{ p}\;\;\text{ and } \left(\frac{a}{p}\right) \in \{-1,0,1\}$$.

where Legendre's symbol is defined as:

$$\left(\frac{a}{p}\right) = \begin{cases}\;\;\,1 \text{ if } a \text{ is a quadratic residue modulo}\ p\text{ and } a \not\equiv 0\pmod{p} \\-1 \text{ if } a \text{ is a quadratic non-residue modulo}\ p\\\;\;\,0 \text{ if } a \equiv 0 \pmod{p}. \end{cases}$$

$\newcommand{Zp}{\mathbb{Z}/p\mathbb{Z}}$Among the many proofs of these facts, let me mention one that uses basically only Fermat's little theorem, and then the fact that a polynomial of degree $n$ over a field has at most $n$ roots. And then of course you need to know that $\Zp$ is a field, for $p$ prime.

I take $p$ to be an odd prime.

If $0 \ne b \in \Zp$, then the equation $$x^{2} = b^{2}$$ has the two solutions $x = b, -b$, and no more, because $x^{2} - b^{2}$ is a polynomial of degree $2$ over the field $\Zp$.

It follows that there are $$\frac{p-1}{2}$$ non-zero squares in $\Zp$.

If $0 \ne b \in \Zp$, we have $$(b^{2})^{(p-1)/2} = 1,$$ so if $a = b^{2}$ is a non-zero square, then $$a^{(p-1)/2} = 1.$$

In other words, the non-zero squares in $\Zp$ are roots of the polynomial $$f = x^{(p-1)/2} - 1.$$ Since there are $(p-1)/2$ squares, and $f$ has degree $(p-1)/2$, the non-zero squares are exactly the roots of the $f$.

So if $a$ is a non-square, we have $a^{(p-1)/2} \ne 1$. Since $$(a^{(p-1)/2})^{2} = 1,$$ we have that $a^{(p-1)/2}$ is a root of $x^{2} - 1$, and it is different from $1$, so $a^{(p-1)/2} = -1$.