Quadratic Residues
Let $a \in \mathbb{Z}_n$. We say $a$ is a quadratic residue if there exists some $x$ such that $x^2 = a$. Otherwise $a$ is a quadratic nonresidue.
Efficiently distinguishing a quadratic residue from a nonresidue modulo $N = p q$ for primes $p, q$ is an open problem. This is exploited by several cryptosystems, such as GoldwassserMicali encryption, or Cocks identitybased encryption. More general variants of this problem underlie other cryptosystems such as Paillier encryption.
Let $p$ be a prime. From now assume $p \gt 2$, as the case $p = 2$ is trivial. Let $g$ be a generator of $\mathbb{Z}_p^*$. Any $a \in \mathbb{Z}_p^*$ can be written as $g^k$ for some $k \in \{1,...,p1\}$.
Say $k$ is even. Write $k = 2m$. Then $(g^m)^2 = a$, so $a$ is a quadratic residue. Exactly half of $\{1,...,p1\}$ is even (since $p$ is odd), hence at least half of the elements of $\mathbb{Z}_p^*$ are quadratic residues.
Suppose we have $b^2 = a$. Then $(b)^2 = a$ as well, and since $b \ne b$ (since $p \gt 2$) every quadratic residue has at least two square roots (actually we know from studying polynomials there can be at most two), thus at most half the elements of $\mathbb{Z}_p^*$ are quadratic residues. (Otherwise there are more square roots than elements!)
Thus exactly half of $\mathbb{Z}_p^*$ are quadratic residues, and they are the even powers of $g$.
Given $a = g^k$, consider the effect of exponentiating by $(p1)/2$. If $k$ is odd, say $k = 2m + 1$, we get
The square of $g^{(p1)/2}$ is $g^{p1} = 1$, so $g^{(p1)/2}$ is $1$ or $1$. But $g$ has order $p1$ ($g$ is a generator) thus we must have $g^{(p1)/2} = 1$.
If $k$ is even, say $k = 2m$, then $a^{(p1)/2} = {g^{(p1)}}^m = 1$.
Thus one way to tell if $a$ is a quadratic residue is to compute $a^{(p1)/2}$: if the result is $1$, then $a$ is a quadratic residue, otherwise the result is $1$ and $a$ is a quadratic nonresidue.
Example: In $\mathbb{Z}_p$, if $(p1)/2$ is even (so $p = 1 \pmod {4}$), then $1$ is a quadratic residue, otherwise $1$ is a quadratic nonresidue.
The Legendre Symbol
This fact (sometimes called Euler’s Criterion) is so useful that we define the Legendre symbol for odd primes $p$ and integers $a$ by
The symbol can also be written as $(ap)$.
Thus:

$\left(\frac{a}{p}\right) = 1$ if $a$ is a quadratic residue of $p$

$\left(\frac{a}{p}\right) = 1$ if $a$ is a quadratic nonresidue of $p$

$\left(\frac{a}{p}\right) = 0$ if $a = 0$ modulo $p$
Some basic properties: for any integer $b$
and for any $r$ coprime to $p$