[proofplan]
We work inside the [cyclic group](/page/Cyclic%20Group) $G=(\mathbb{Z}/p\mathbb{Z})^\times$ generated by $\bar{g}$. The key point is that squares in this cyclic group are exactly the even powers of the generator. Thus an even exponent $k$ makes $\bar{a}$ a square, while an odd exponent cannot make $\bar{a}$ a square because equality of powers of $\bar{g}$ is controlled modulo the even number $p-1$.
[/proofplan]
[step:Fix the cyclic group and the parity of the exponent]
Define
\begin{align*}
G := (\mathbb{Z}/p\mathbb{Z})^\times.
\end{align*}
Let $1_G$ denote the identity element of $G$. Since $p$ is prime, $G$ consists of the $p-1$ nonzero residue classes modulo $p$. Since $\bar{g}$ generates $G$, the order of $\bar{g}$ in $G$ is $p-1$.
If $\ell \in \mathbb{Z}$ is another integer satisfying $\bar{a}=\bar{g}^{\ell}$, then
\begin{align*}
\bar{g}^{k-\ell}=1_G.
\end{align*}
Because $\bar{g}$ has order $p-1$, this implies $p-1 \mid k-\ell$. Since $p$ is odd, $p-1$ is even, so $k-\ell$ is even. Hence the parity of the exponent representing $\bar{a}$ as a power of $\bar{g}$ is well-defined.
[/step]
[step:Show that even powers of the primitive root are quadratic residues]
Assume first that $k$ is even. Choose $m \in \mathbb{Z}$ such that $k=2m$. Then in $G$,
\begin{align*}
\bar{a}=\bar{g}^{k}=\bar{g}^{2m}=(\bar{g}^{m})^2.
\end{align*}
Thus $\bar{a}$ is a square in $(\mathbb{Z}/p\mathbb{Z})^\times$, equivalently $a$ is a [quadratic residue](/page/Quadratic%20Residue) modulo $p$. Since $p \nmid a$, the definition of the [Legendre symbol](/page/Legendre%20Symbol) gives
\begin{align*}
\left(\frac{a}{p}\right)=1.
\end{align*}
For even $k$, also $(-1)^k=1$, so the desired identity holds in this case.
[/step]
[step:Show that odd powers of the primitive root are quadratic nonresidues]
Assume now that $k$ is odd. We prove that $\bar{a}$ is not a square in $G$. Suppose, for contradiction, that $\bar{a}$ is a square in $G$. Then there exists a class $u \in G$ such that
\begin{align*}
u^2=\bar{a}.
\end{align*}
Since $\bar{g}$ generates $G$, there exists $m \in \mathbb{Z}$ such that $u=\bar{g}^{m}$. Therefore
\begin{align*}
\bar{g}^{2m}=u^2=\bar{a}=\bar{g}^{k}.
\end{align*}
Multiplying by $\bar{g}^{-k}$ in $G$ gives
\begin{align*}
\bar{g}^{2m-k}=1_G.
\end{align*}
Because the order of $\bar{g}$ is $p-1$, we have $p-1 \mid 2m-k$. But $p-1$ is even, while $2m-k$ is odd because $2m$ is even and $k$ is odd. An even integer cannot divide an odd integer, a contradiction.
Hence $\bar{a}$ is not a square in $G$. Since $p \nmid a$, the definition of the Legendre symbol gives
\begin{align*}
\left(\frac{a}{p}\right)=-1.
\end{align*}
For odd $k$, also $(-1)^k=-1$, so the desired identity holds in this case.
[guided]
Assume that $k$ is odd. The goal is to prove that $a$ is a quadratic nonresidue modulo $p$, meaning that no unit square in $\mathbb{Z}/p\mathbb{Z}$ equals $\bar{a}$.
Suppose instead that $\bar{a}$ is a square in the unit group $G=(\mathbb{Z}/p\mathbb{Z})^\times$. Let $1_G$ denote the identity element of $G$. Then there is some element $u \in G$ satisfying
\begin{align*}
u^2=\bar{a}.
\end{align*}
Why can we write $u$ as a power of $\bar{g}$? Because $\bar{g}$ generates $G$ by hypothesis. Thus there exists an integer $m \in \mathbb{Z}$ such that
\begin{align*}
u=\bar{g}^{m}.
\end{align*}
Substituting this into the equation $u^2=\bar{a}$ and using the hypothesis $\bar{a}=\bar{g}^k$, we get
\begin{align*}
\bar{g}^{2m}=u^2=\bar{a}=\bar{g}^{k}.
\end{align*}
Now cancel the common power of $\bar{g}$ inside the group $G$ by multiplying both sides by $\bar{g}^{-k}$. This gives
\begin{align*}
\bar{g}^{2m-k}=1_G.
\end{align*}
Because $p$ is prime, $G$ has $p-1$ elements. Since $\bar{g}$ generates $G$, its order is $p-1$. Therefore a power $\bar{g}^{r}$ equals $1_G$ exactly when $p-1$ divides $r$. Applying this with $r=2m-k$, we obtain
\begin{align*}
p-1 \mid 2m-k.
\end{align*}
This divisibility is impossible by parity. The prime $p$ is odd, so $p-1$ is even. The integer $2m$ is even, and $k$ is odd, so $2m-k$ is odd. No even integer divides an odd integer. This contradiction proves that $\bar{a}$ is not a square in $G$.
Because $p \nmid a$, the Legendre symbol is defined by whether $\bar{a}$ is a square in $(\mathbb{Z}/p\mathbb{Z})^\times$. We have shown that it is not a square, so
\begin{align*}
\left(\frac{a}{p}\right)=-1.
\end{align*}
Since $k$ is odd, $(-1)^k=-1$, and therefore
\begin{align*}
\left(\frac{a}{p}\right)=(-1)^k.
\end{align*}
[/guided]
[/step]
[step:Combine the two parity cases]
The integer $k$ is either even or odd. The even case gives
\begin{align*}
\left(\frac{a}{p}\right)=1=(-1)^k,
\end{align*}
and the odd case gives
\begin{align*}
\left(\frac{a}{p}\right)=-1=(-1)^k.
\end{align*}
Therefore, in all cases,
\begin{align*}
\left(\frac{a}{p}\right)=(-1)^k.
\end{align*}
This proves the theorem.
[/step]
