$\newcommand{\kron}[2]{\left( \frac{#1}{#2} \right)}$ It's easy to use Quadratic Reciprocity to show that $\kron{5}{p} = \kron{p}{5} = 1$ when $p \equiv \pm 1 \pmod 5$, and is $-1$ when $p \equiv \pm 2 \pmod 5$.
I'm interested in an elementary, direct proof of when this happens without appealing to either quadratic reciprocity directly or to things like Gauss's lemma (which is sort of like quadratic reciprocity in disguise). For example, this answer gives a direct proof of $\kron 2p$.
For $p \pmod 5$, this is not so bad. For instance, if $p \equiv 1 \pmod 5$, then one can use that $\left( \mathbb{Z}/p\mathbb{Z} \right)^\times$ is cyclic of order divisible by $5$ to get an element of order $5$, and then proceed as in this question.
But what about when $p \not \equiv 1 \pmod 5$? In particular, how might we handle when $p \equiv -1 \pmod 5$?