[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.[/step]

[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: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]