Help with proof of Euler's criterion

Question

Problem

This problem is about finding square roots modulo a prime $p$.

(a) Prove that $x^2 \equiv y^2 \pmod p$ if and only if $x \equiv y \pmod p$ or $x \equiv -y \pmod p$.

An integer $x$ is called a square root of $n$ mod $p$ when $x^2 \equiv n \pmod p$. An integer with a square root is called a square mod $p$. Assume that $p$ is an odd prime and $n \not \equiv 0 \pmod p$. It turns out there is a simple test we can perform to see if $n$ is a square mod $p$:

Euler's Criterion

i. If $n$ is a square modulo $p$, then $n^{(p-1)/2} \equiv 1 \pmod p$.

ii. If $n$ is not a square modulo $p$, then $n^{(p-1)/2} \equiv -1 \pmod p$.

(b) Prove Case (i) of Euler's Criterion.

(c) Prove Case (ii) of Euler's Criterion.

Solution

(a) Prove both directions of the if and only if:

1. Assume that $x^2 \equiv y^2 \pmod p$. Then:

$$\begin{align} &x^2 - y^2 \equiv 0 \pmod p \\ &\Rightarrow(x+y)(x-y) \equiv 0 \pmod p \\ &\Rightarrow p\text{ | }(x+y)(x-y) \\ &\Rightarrow [p\text{ | }(x+y)]\text{ or }[p\text{ | }(x-y)] &\text{(since }p\text{ is prime)} \\ &\Rightarrow [x+y \equiv 0 \pmod p]\text{ or }[x-y \equiv 0 \pmod p] \\ &\Rightarrow [x \equiv -y \pmod p]\text{ or }[x \equiv y \pmod p] \end{align}$$

2. Assume that $x\equiv y \pmod p$ or $x\equiv -y \pmod p$. In both cases, squaring both sides gives $x^2\equiv y^2 \pmod p$.

(b) Assume that $x^2 \equiv n \pmod p$ for some $x, n, p$.

Since $n \not \equiv 0 \pmod p$ and $p$ is prime, $n$ and $p$ are relatively prime. Then, $x^2$ and $p$ are also relatively prime. Therefore, $x$ must be relatively prime to $p$. Then, by Fermat's theorem, $x^{p - 1} \equiv 1 \pmod p$. So:

$$\textrm{rem}(n^{(p-1)/2}, p) = \mathrm{rem}((x^2)^{(p-1)/2}, p) = \mathrm{rem}(x^{p-1}, p) = 1,$$

which proves (i).

(c) Assume that $n$ is not a square modulo $p$.

Since $n$ and $p$ are relatively prime, by Fermat's theorem, $n^{p - 1} \equiv 1 \pmod p$. Since $p$ is odd, $p - 1$ is even, so this can be rewritten as:

$$(n^{(p - 1)/2})^2 \equiv 1 \pmod p.$$

Then, from (a), it must be the case that either $n^{(p - 1)/2} \equiv 1 \pmod p$ or $n^{(p - 1)/2} \equiv -1 \pmod p$.

I got stuck at this point. I don't know how to infer, from the above facts, that $n^{(p-1)/2} \equiv -1 \pmod p$. Any hints on how to proceed?

Answer 1

Let $g$ be a primitive root in modulo $p$. Then for an integer $x$ relatively prime to $n$ we have, $x\equiv g^i$(mod $p$), for some $i=1,2,\dots,p-1$. Similarly since, $gcd(n,p)=1$, so there are some $j=1,2,\dots,p-1$ such that $n\equiv g^j$(mod $p$).

Now, there is an integer $x$ relatively prime to $p$ satisfying $x^2\equiv n$(mod $p$) if and only if,

$g^{2i}\equiv g^j$ (mod $p$)

$\Leftrightarrow$ $2i\equiv j$ (mod $p-1$)$\dots$ (1)

Hence $n$ is a quadratic residue in module $p$

$\Leftrightarrow$ (1) has a solution in $i$.

$\Leftrightarrow$ $gcd(2,p-1)=2$ divides $j$.

Now if $2|j$ then $j=2t$ for some integer t. Then

$n^{\frac{p-1}{2}}\equiv (g^t)^{p-1} \equiv 1$ (mod $p$).

Next, if 2 does not divide $j$ then $\frac{p-1}{2}j$ is not a multiple of $p-1$. So

$n^{\frac{p-1}{2}}\equiv g^{\frac{p-1}{2}j} \not\equiv 1$ (mod $p$). [ Since $g$ is primitive in module $p$ so $g^s\equiv 1$ (mod $p$) for $s=p-1$ but not for any $s=1,\dots,p-2$.]

Now from (a) then we have, $n^{\frac{p-1}{2}}\equiv -1$ (mod $p$).

Hence $n$ is quadratic residue module $p$ or not according to, $n^{\frac{p-1}{2}}\equiv 1$ or, $n^{\frac{p-1}{2}}\equiv -1$.