Euler's criterion

Since $(\mathbb{Z}/p\mathbb{Z})^{*}$ is cyclic of order $p-1$ (a standard fact for prime moduli), fix a primitive root $g$ and write $a \equiv g^k \pmod p$ for some $0 \le k \le p-2$. The quadratic residues modulo $p$ are exactly the even powers of $g$: if $a=g^{2m}$ then $x=g^m$ satisfies $x^2\equiv a$, and conversely every square $x^2=(g^j)^2=g^{2j}$ is an even power. So $a$ is a quadratic residue exactly when $k$ is even.

Now compute $a^{(p-1)/2} \equiv g^{k(p-1)/2} \pmod p$. If $k$ is even, write $k=2m$; then $g^{k(p-1)/2}=g^{m(p-1)}=(g^{p-1})^m\equiv 1^m=1\pmod p$ by Fermat's little theorem, matching the residue case.

If $k$ is odd, then $g^{k(p-1)/2}$ is a square root of $g^{k(p-1)}=(g^{p-1})^k\equiv 1\pmod p$, so $a^{(p-1)/2}\equiv \pm 1$. It cannot be $1$: if it were, the order of $g$ would have to divide $k(p-1)/2$, but $\operatorname{ord}(g)=p-1$ and $k$ is odd means $k(p-1)/2$ is not a multiple of $p-1$ unless $(p-1)/2$ already is, contradicting that $g$ is a primitive root of exact order $p-1$. Hence $a^{(p-1)/2}\equiv -1\pmod p$ exactly when $k$ is odd, i.e. exactly when $a$ is a nonresidue.

Combining both cases: $a^{(p-1)/2}\equiv 1\pmod p$ iff $a$ is a quadratic residue, and $\equiv -1$ otherwise, which is precisely the statement $\left(\dfrac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$.