| | |
Suppose $p$ is an odd prime, and $b$ is a positive integer where $p \not\mid b$.
If $R$ the set of least residues $r$ modulo $p$ of products of the form $b \cdot a$ where $a$ is odd and $0 \lt a \lt p$, and $t$ is the number of elements in $R$ which are even, then $(b/p) = (-1)^t$.
Proof:
Suppose $p = 2m + 1$, then there are $m$ positive, odd $a < p$. As such, label the elements of the set $R$ so that $r_1,r_2,\ldots,r_t$ are even, and $r_{t+1},r_{t+2},\ldots,r_m$ are odd.
Let $a_1,a_2,\ldots,a_m$ be the distinct positive integers less than $p$, ordered so that $r_i \equiv b \cdot a_i\pmod{p}$.
Also, let $A = \{(p-r_1),(p-r_2),\ldots,(p-r_t),r_{t+1},r_{t+2},\ldots,r_m\}$.
We claim the following:
The elements of $A$ are all positive and less than $p$, as $0 \lt r_i \lt p$, for each $r_i$, by virtue of each $r_i$ being a least residue modulo $p$.
The elements of $A$ are all odd. To see this, recall $p$ is an odd prime, and $r_i$ is even when $i \le t$. Thus, each $p-r_i \in A$ is odd. Also, $r_i$ is odd when $i > t$, so each $r_i \in A$ must be odd.
The elements of $A$ are distinct. To demonstrate this, first note that $A$ is comprised of two types of elements - those of the form $p-r_i$ and those of the form $r_i$. We will show that all elements of the form $p-r_i$ are distinct from one another, all elements of the form $r_i$ are distinct from one another, and no element of $A$ in the first form ever equals an element of $A$ in the second form. We argue each of these indirectly:
Suppose $p-r_i = p-r_j$ for $i \not= j$. Then $p-r_i \equiv p-r_j\pmod{p}$, which implies $r_i \equiv r_j\pmod{p}$, and in turn $ba_i \equiv ba_j\pmod{p}$. Since $p \not\mid b$, $b$ has a multiplicative inverse $\pmod{p}$, so $a_i \equiv a_j\pmod{p}$. Given that $0 \lt a_i,a_j \lt p$, we have $a_i = a_j$, which contradicts our previous conclusion that $a_1,a_2,\ldots,a_m$ are distinct.
Suppose $r_i = r_j$ for $i \not= j$. Then $r_i \equiv r_j\pmod{p}$, which in the same way leads to $a_i = a_j$, and again contradicts the distinctness of the elements $a_1,a_2,\ldots,a_m$.
Finally, suppose $p-r_i = r_j$ with $i \le t$, $j \gt t$. Then, $p = r_i + r_j \equiv ba_i + ba_j\pmod{p}$. So $p \mid b(a_i+a_j) - p$, which in turn implies $p \mid b(a_i+a_j)$. Since we know $p \not\mid b$, it must be the case that $p \mid (a_i+a_j)$. Recall, $0 \lt a_i,a_j \lt p$ so $0 \lt a_i+a_j \lt 2p$, making $a_i+a_j$ a multiple of $p$ strictly between $0$ and $2p$. Thus, $a_i+a_j = p$. This is impossible, however, as $a_i+a_j$ is even, since both $a_i$ and $a_j$ are odd, and $p$ is an odd prime.
Thus, the elements of $A$ are distinct, positive odd integers less than $p$. Recalling that there are only $m$ such integers, $a_1, a_2,\ldots,a_m$ and there are $m$ elements in $A$, it must be the case that the elements of $A$ are exactly $a_1, a_2,\ldots,a_m$ - just perhaps in a different order.
Importantly, that means that modulo $p$ we have: $$\begin{array}{rcl} a_1 a_2 \cdots a_m &\equiv& (p-r_1)(p-r_2)\cdots(p-r_t) r_{t+1} r_{t+2} \cdots r_m\\ &\equiv& (-1)^t \cdot r_1 r_2 \cdots r_m\\ &\equiv& (-1)^t \cdot (ba_1)(ba_2) \cdots (ba_m)\\ &\equiv& (-1)^t b^m a_1 a_2 \cdots a_m \pmod{p} \end{array}$$ Each $a_i$ is relatively prime to $p$, so we can multiply by their multiplicative inverses to arrive at $1 \equiv (-1)b^m\pmod{p}$. Equivalently, $$b^m \equiv (-1)^t \pmod{p}$$ Recalling that $p = 2m+1$, we have $$b^{(p-1)/2} \equiv (-1)^t \pmod{p}$$ Finally, applying Euler's Criterion, we arrive at $$\left( \frac{b}{p} \right) = (-1)^t$$