The Legendre Symbol

Introduction:

The Legendre Symbol tells us that whether a number $x \in \mathbf{Z}^*_p$ where p is prime is a perfect square (also called quadratic residue).

Definition:

For a prime p and $x \in \mathbf{Z}^*_p$, the Legendre Symbol $\mathbf{J}_p(x)$ is defined as:
$\mathbf{J}_p(x) = \begin{cases} 1 & \mbox{if } x\mbox{ is a perfect square in }\mathbf{Z}^*_p \\ 0 & \mbox{if }gcd(x,p) \neq 1 \\ -1 & \mbox{if } x\mbox{ is not a perfect square in }\mathbf{Z}^*_p \end{cases}$
The Legendre Symbol is computed by $\mathbf{J}_p(x) \equiv x^{\frac{p-1}{2}} \mbox{ mod } p$

Discussion and Proof:

• Since p is prime, $x = kp$ where $k \in \mathbb{Z}$ if $gcd(x,p) \neq 1$. As a result, $\mathbf{J}_p(x) = (kp)^{\frac{p-1}{2}} = 0 \mbox{ mod } p$
• If x is a perfect square in $\mathbf{Z}^*_p$ and g is a generator of $\mathbf{Z}^*_p$, x can be written as $g^{2i} \mbox{ mod } p \mbox{ where } 1 \leq 2i \leq p-1$. As a result, $\mathbf{J}_p(x) = g^{\frac{2i(p-1)}{2}} = g^{i(p-1)} = 1 \mbox{ mod }p$
• If x is not a perfect square in $\mathbf{Z}^*_p$ and g is a generator of $\mathbf{Z}^*_p$, x can be written as $g^{i} \mbox{ mod } p \mbox{ where } 1 \leq i \leq p-1$. Since i is odd, $\frac{i(p-1)}{2}$ is not an integer and $\mathbf{J}_p(x) = g^{\frac{i(p-1)}{2}} = \sqrt{1} = \pm{1}$. However, this does not quite match the definition. To continue the proof, we have to prove thatx is a perfect square in $\mathbf{Z}^*_p$ if and only if $x^{\frac{p-1}{2}} = 1 \mbox{ mod } p$:
  $\Rightarrow$ Assume x is a perfect square in $\mathbf{Z}^*_p$, x can be written as $g^{2i} \mbox{ mod } p \mbox{ where } 1 \leq 2i \leq p-1$ and $\mathbf{J}_p(x) = g^{\frac{2i(p-1)}{2}} = g^{i(p-1)} = 1 \mbox{ mod }p$
  $\Leftarrow$ Assume $x^{\frac{p-1}{2}} = 1 \mbox{ mod } p$. Since $x \in \mathbf{Z}^*_p$, x can be written as $g^{i} \mbox{ mod } p$ where $1 \leq i \leq p-1$. Since g is a generator of $\mathbf{Z}^*_p$, g has the order $(p-1)$. Only $g^{p-1} \equiv 1 \mbox{ mod } p$ and $g^i \not\equiv 1 \mbox{ for } i < p-1$. As a result, $(p-1)$  must divide $\frac{i(p-1)}{2}$ and so i is even and x is a perfect square in $\mathbf{Z}^*_p$
  As a result, $\mathbf{J}_p(x) \neq 1$ if x is not a perfect square in $\mathbf{Z}^*_p$ and so $\mathbf{J}_p(x) = -1$