[proofplan]
The Jacobi symbol is defined as a product of Legendre symbols over the prime factorisations of $m$ and $n$. We first dispatch the case $(m, n) > 1$, in which both sides vanish. When $(m, n) = 1$, we factor $m = p_1 \cdots p_k$ and $n = q_1 \cdots q_\ell$ into odd primes with multiplicity and expand $\left(\frac{m}{n}\right)$ and $\left(\frac{n}{m}\right)$ as double products of Legendre symbols $\left(\frac{p_i}{q_j}\right)$ and $\left(\frac{q_j}{p_i}\right)$. The classical [Quadratic Reciprocity for Legendre symbols](/theorems/???) provides an exchange at each prime pair, at the cost of a sign $(-1)^{(p_i - 1)/2 \cdot (q_j - 1)/2}$. Collecting the signs yields a global factor $(-1)^{rs}$, where $r$ and $s$ count the prime factors of $m$ and $n$ (with multiplicity) that are $\equiv 3 \pmod 4$. A parity argument identifies $rs$ with $\frac{m-1}{2} \cdot \frac{n-1}{2}$ modulo $2$, completing the proof.
[/proofplan]
[step:Dispose of the non-coprime case]
Suppose $(m, n) > 1$. Let $p$ be a prime dividing both $m$ and $n$; since $m, n$ are odd, $p$ is odd. Then $p$ appears in the prime factorisation of $n$, so the Jacobi symbol $\left(\frac{m}{n}\right)$ contains the factor $\left(\frac{m}{p}\right)$, which is a Legendre symbol. Since $p \mid m$, $\left(\frac{m}{p}\right) = 0$. Therefore $\left(\frac{m}{n}\right) = 0$, and symmetrically $\left(\frac{n}{m}\right) = 0$. Both sides of the asserted identity equal $0$, so the identity holds. In what follows we may assume $(m, n) = 1$.
[/step]
[step:Expand both sides into double products of Legendre symbols]
Assume $(m, n) = 1$. Write the prime factorisations with multiplicity:
\begin{align*}
m &= p_1 p_2 \cdots p_k, & n &= q_1 q_2 \cdots q_\ell,
\end{align*}
where each $p_i$ and each $q_j$ is an odd prime. Since $(m, n) = 1$, no $p_i$ equals any $q_j$.
By the multiplicativity of the Jacobi symbol in both arguments (from [Properties of the Jacobi Symbol](/theorems/1722)),
\begin{align*}
\left(\frac{m}{n}\right) &= \prod_{j=1}^{\ell} \left(\frac{m}{q_j}\right) = \prod_{j=1}^{\ell} \prod_{i=1}^{k} \left(\frac{p_i}{q_j}\right) = \prod_{i=1}^{k} \prod_{j=1}^{\ell} \left(\frac{p_i}{q_j}\right),
\end{align*}
and symmetrically
\begin{align*}
\left(\frac{n}{m}\right) &= \prod_{i=1}^{k} \prod_{j=1}^{\ell} \left(\frac{q_j}{p_i}\right).
\end{align*}
Each factor on the right-hand side is a Legendre symbol between distinct odd primes (since $p_i \neq q_j$).
[/step]
[step:Apply Legendre Quadratic Reciprocity at each prime pair]
For each pair $(i, j)$, both $p_i$ and $q_j$ are distinct odd primes. The hypotheses of [Quadratic Reciprocity for the Legendre Symbol](/theorems/???) are met, and we obtain
\begin{align*}
\left(\frac{p_i}{q_j}\right) &= (-1)^{\frac{p_i - 1}{2} \cdot \frac{q_j - 1}{2}} \left(\frac{q_j}{p_i}\right).
\end{align*}
Taking the double product over $i$ and $j$ and using Step 2:
\begin{align*}
\left(\frac{m}{n}\right) &= \prod_{i=1}^{k} \prod_{j=1}^{\ell} \left(\frac{p_i}{q_j}\right) = \prod_{i=1}^{k} \prod_{j=1}^{\ell} (-1)^{\frac{p_i - 1}{2} \cdot \frac{q_j - 1}{2}} \left(\frac{q_j}{p_i}\right) = \varepsilon \cdot \left(\frac{n}{m}\right),
\end{align*}
where the global sign is
\begin{align*}
\varepsilon &= \prod_{i=1}^{k} \prod_{j=1}^{\ell} (-1)^{\frac{p_i - 1}{2} \cdot \frac{q_j - 1}{2}} = (-1)^{E}, & E &= \sum_{i=1}^{k} \sum_{j=1}^{\ell} \frac{p_i - 1}{2} \cdot \frac{q_j - 1}{2}.
\end{align*}
[/step]
[step:Identify $E$ modulo $2$ with $rs$, where $r, s$ count odd primes $\equiv 3 \pmod 4$]
Define
\begin{align*}
r &= \#\{i \in \{1, \ldots, k\} : p_i \equiv 3 \pmod 4\}, & s &= \#\{j \in \{1, \ldots, \ell\} : q_j \equiv 3 \pmod 4\}.
\end{align*}
For any odd prime $p$, $\frac{p-1}{2} \equiv 0 \pmod 2$ if $p \equiv 1 \pmod 4$, and $\frac{p-1}{2} \equiv 1 \pmod 2$ if $p \equiv 3 \pmod 4$. Therefore the factorised double sum separates:
\begin{align*}
E &= \left(\sum_{i=1}^{k} \frac{p_i - 1}{2}\right) \left(\sum_{j=1}^{\ell} \frac{q_j - 1}{2}\right).
\end{align*}
Reducing each factor modulo $2$,
\begin{align*}
\sum_{i=1}^{k} \frac{p_i - 1}{2} &\equiv r \pmod 2, & \sum_{j=1}^{\ell} \frac{q_j - 1}{2} &\equiv s \pmod 2,
\end{align*}
since only the primes $\equiv 3 \pmod 4$ contribute an odd value to the sum. Hence $E \equiv rs \pmod 2$, and
\begin{align*}
\varepsilon &= (-1)^{E} = (-1)^{rs}.
\end{align*}
[/step]
[step:Match $rs$ to $\frac{m-1}{2} \cdot \frac{n-1}{2}$ modulo $2$]
By iterated application of the parity identity $\frac{ab - 1}{2} \equiv \frac{a-1}{2} + \frac{b-1}{2} \pmod 2$ for odd $a, b$ (proved as Step 4 of the [Properties of the Jacobi Symbol](/theorems/1722)), we have
\begin{align*}
\frac{m - 1}{2} &\equiv \sum_{i=1}^{k} \frac{p_i - 1}{2} \equiv r \pmod 2, & \frac{n - 1}{2} &\equiv \sum_{j=1}^{\ell} \frac{q_j - 1}{2} \equiv s \pmod 2.
\end{align*}
The formal induction is identical to that of [Properties of the Jacobi Symbol](/theorems/1722), Step 5: chain $k - 1$ (respectively $\ell - 1$) applications of the parity identity along the factorisation $m = p_1(p_2(\cdots))$ (respectively for $n$).
Consequently,
\begin{align*}
rs &\equiv \frac{m-1}{2} \cdot \frac{n-1}{2} \pmod 2,
\end{align*}
and
\begin{align*}
\varepsilon &= (-1)^{rs} = (-1)^{\frac{m-1}{2} \cdot \frac{n-1}{2}}.
\end{align*}
[guided]
The point is to identify the elementary-symmetric quantity $rs$ — the product of counts of primes $\equiv 3 \pmod 4$ in $m$ and $n$ — with the compound quantity $\frac{m-1}{2} \cdot \frac{n-1}{2}$, modulo $2$.
For odd $x$, exactly one of $\frac{x - 1}{2} \equiv 0$ or $\frac{x - 1}{2} \equiv 1$ holds modulo $2$, according to $x \equiv 1$ or $3 \pmod 4$. So $\frac{x - 1}{2} \bmod 2$ is the indicator function of "$x \equiv 3 \pmod 4$".
The parity identity $\frac{ab-1}{2} \equiv \frac{a-1}{2} + \frac{b-1}{2} \pmod 2$ (for odd $a, b$), established in the proof of [Properties of the Jacobi Symbol](/theorems/1722), tells us this indicator is additive modulo $2$ under products of odd numbers. Applied inductively along the prime factorisation of $m$, it gives $\frac{m-1}{2} \equiv r \pmod 2$. Similarly $\frac{n-1}{2} \equiv s \pmod 2$. Multiplying: $\frac{m-1}{2} \cdot \frac{n-1}{2} \equiv rs \pmod 2$.
One might worry whether $rs$ and $\frac{m-1}{2} \cdot \frac{n-1}{2}$ could differ by an even integer (they can, but that does not affect the sign $(-1)^{rs}$). The parity match is exactly what we need.
[/guided]
[/step]
[step:Assemble the Jacobi reciprocity law]
Combining Steps 3 and 5:
\begin{align*}
\left(\frac{m}{n}\right) &= \varepsilon \cdot \left(\frac{n}{m}\right) = (-1)^{\frac{m-1}{2} \cdot \frac{n-1}{2}} \left(\frac{n}{m}\right).
\end{align*}
When $(m, n) = 1$, both Jacobi symbols are $\pm 1$, so multiplying both sides by $\left(\frac{n}{m}\right)$ (which is its own inverse) yields
\begin{align*}
\left(\frac{m}{n}\right) \left(\frac{n}{m}\right) &= (-1)^{\frac{m-1}{2} \cdot \frac{n-1}{2}}.
\end{align*}
This, together with the case $(m, n) > 1$ handled in Step 1, proves Jacobi reciprocity.
[/step]
