[proofplan] For each $j \in \{1, \ldots, (p-1)/2\}$, we write $aj \equiv \epsilon_j c_j \pmod p$ with $\epsilon_j \in \{\pm 1\}$ and $c_j \in \{1, \ldots, (p-1)/2\}$ by folding $aj$ into the symmetric residue system $\{-\frac{p-1}{2}, \ldots, \frac{p-1}{2}\} \setminus \{0\}$. The key observation is that the $c_j$ are a permutation of $\{1, \ldots, (p-1)/2\}$. Multiplying all the congruences and cancelling the factorial yields $a^{(p-1)/2} \equiv (-1)^\mu \pmod p$, where $\mu$ counts the negative signs. [Euler's Criterion](/theorems/???) then converts the left-hand side into $\left(\frac{a}{p}\right)$. [/proofplan] [step:Reduce each multiple $aj$ into the symmetric residue system] Let $p$ be an odd prime and $a \in \mathbb{Z}$ with $(a, p) = 1$. For each $j \in \{1, \ldots, (p-1)/2\}$, the residue of $aj$ modulo $p$ is nonzero (since $p \nmid aj$), so it lies in one of the two halves \begin{align*} H^+ &= \left\{1, 2, \ldots, \tfrac{p-1}{2}\right\}, & H^- &= \left\{\tfrac{p+1}{2}, \ldots, p-1\right\}. \end{align*} Define \begin{align*} \epsilon_j &= \begin{cases} +1 & aj \bmod p \in H^+, \\ -1 & aj \bmod p \in H^-, \end{cases} & c_j &= \begin{cases} aj \bmod p & \text{if } \epsilon_j = +1, \\ p - (aj \bmod p) & \text{if } \epsilon_j = -1. \end{cases} \end{align*} Then $c_j \in \{1, \ldots, (p-1)/2\}$ and \begin{align*} a j \equiv \epsilon_j c_j \pmod{p}. \end{align*} By definition, $\mu = \#\{ j : \epsilon_j = -1 \}$. [/step] [step:Show the map $j \mapsto c_j$ is a permutation of $\{1, \ldots, (p-1)/2\}$] [claim:The values $c_1, \ldots, c_{(p-1)/2}$ are all distinct] [proof] Suppose $c_j = c_k$ for some $j, k \in \{1, \ldots, (p-1)/2\}$. Then $\epsilon_j a j \equiv c_j \equiv c_k \equiv \epsilon_k a k \pmod p$, so \begin{align*} \epsilon_j a j - \epsilon_k a k \equiv 0 \pmod{p}, \qquad\text{i.e.}\qquad a(\epsilon_j j - \epsilon_k k) \equiv 0 \pmod{p}. \end{align*} Since $(a, p) = 1$, $a$ is a unit modulo $p$, so $\epsilon_j j \equiv \epsilon_k k \pmod p$. Hence either $j \equiv k \pmod p$ (if $\epsilon_j = \epsilon_k$) or $j \equiv -k \pmod p$ (if $\epsilon_j = -\epsilon_k$). In the first case, $1 \le j, k \le (p-1)/2 < p$ forces $j = k$. In the second case, $j + k \equiv 0 \pmod p$ with $2 \le j + k \le p - 1$, which is impossible. Thus $j = k$. [/proof] [/claim] Since $c_j \in \{1, \ldots, (p-1)/2\}$ and the $c_j$ are $(p-1)/2$ distinct elements of this set, \begin{align*} \{c_1, c_2, \ldots, c_{(p-1)/2}\} = \left\{1, 2, \ldots, \tfrac{p-1}{2}\right\} \end{align*} as sets, i.e. $j \mapsto c_j$ is a permutation. [/step] [step:Multiply the congruences and extract the sign] Multiplying the relations $a j \equiv \epsilon_j c_j \pmod p$ over $j = 1, \ldots, (p-1)/2$, \begin{align*} a^{(p-1)/2} \prod_{j=1}^{(p-1)/2} j \equiv \prod_{j=1}^{(p-1)/2} \epsilon_j c_j \equiv \left(\prod_{j=1}^{(p-1)/2} \epsilon_j\right) \prod_{j=1}^{(p-1)/2} c_j \pmod{p}. \end{align*} By the previous step, $\prod_{j} c_j = \prod_{j} j = \left(\frac{p-1}{2}\right)!$. Writing $\prod_j \epsilon_j = (-1)^\mu$ (since exactly $\mu$ of the $\epsilon_j$ equal $-1$), \begin{align*} a^{(p-1)/2} \cdot \left(\tfrac{p-1}{2}\right)! \equiv (-1)^\mu \cdot \left(\tfrac{p-1}{2}\right)! \pmod{p}. \end{align*} Each factor $1, 2, \ldots, (p-1)/2$ is coprime to $p$ (since $1 \le j < p$), so $\left(\frac{p-1}{2}\right)!$ is a unit modulo $p$. Cancelling it, \begin{align*} a^{(p-1)/2} \equiv (-1)^\mu \pmod{p}. \end{align*} [/step] [step:Invoke Euler's criterion and upgrade the congruence to an equality in $\{\pm 1\}$] By [Euler's Criterion](/theorems/???), whose hypotheses ($p$ odd prime, $(a, p) = 1$) are both given, \begin{align*} \left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \equiv (-1)^\mu \pmod{p}. \end{align*} Both $\left(\frac{a}{p}\right)$ and $(-1)^\mu$ lie in $\{+1, -1\}$. The difference of any two distinct elements of $\{+1, -1\}$ is $\pm 2$, and $p$ is odd, so $p \nmid 2$. Hence a congruence modulo $p$ between elements of $\{+1, -1\}$ forces equality as integers: \begin{align*} \left(\frac{a}{p}\right) = (-1)^\mu. \end{align*} [guided] We need to bridge from the congruence $\left(\frac{a}{p}\right) \equiv (-1)^\mu \pmod p$ to equality of integers. A priori, $x \equiv y \pmod p$ permits $x - y = kp$ with $k \ne 0$. The way out: both sides live in $\{+1, -1\}$. The left side is a Legendre symbol of a unit modulo $p$, which equals $\pm 1$ by definition; the right side is a signed power of $-1$. For $x, y \in \{+1, -1\}$, the only values of $x - y$ are $-2, 0, +2$. Since $p$ is odd, $p \mid 2$ is false, so $p \mid (x-y)$ forces $x - y = 0$. The hypothesis "$p$ is odd" (part of "$p$ is an odd prime") is exactly what we need. Therefore \begin{align*} \left(\frac{a}{p}\right) = (-1)^\mu. \end{align*} [/guided] [/step]