[proofplan] The Jacobi symbol is defined multiplicatively over the prime factorisation $n = p_1 \cdots p_k$ (with repetition) by $\left(\frac{a}{n}\right) = \prod_{j=1}^{k} \left(\frac{a}{p_j}\right)$, where each factor on the right is a Legendre symbol. Properties (i) and (ii) transfer directly from the corresponding Legendre-symbol identities by taking products. Properties (iii) and (iv) follow the same blueprint but require an auxiliary exponent identity to show that multiplicativity of $(-1)^{(n-1)/2}$ and $(-1)^{(n^2-1)/8}$ in $n$ matches the multiplicativity built into the Jacobi symbol. Both identities reduce to elementary congruences valid for odd integers. [/proofplan] [step:Record the defining multiplicativity of the Jacobi symbol] Let $n \geq 1$ be odd with prime factorisation (including multiplicity) \begin{align*} n &= p_1 p_2 \cdots p_k, \end{align*} where each $p_j$ is an odd prime. The Jacobi symbol is the map \begin{align*} \left(\frac{\,\cdot\,}{n}\right) : \mathbb{Z} &\to \{-1, 0, 1\} \\ a &\mapsto \prod_{j=1}^{k} \left(\frac{a}{p_j}\right), \end{align*} where each factor $\left(\frac{a}{p_j}\right)$ is the Legendre symbol modulo the prime $p_j$. By construction the Jacobi symbol is multiplicative in the lower argument: for odd $m, n \geq 1$, \begin{align*} \left(\frac{a}{mn}\right) &= \left(\frac{a}{m}\right) \left(\frac{a}{n}\right), \end{align*} because the prime factorisation of $mn$ is the concatenation of those of $m$ and $n$. [/step] [step:Derive congruence invariance (i) from the Legendre case] Suppose $a \equiv b \pmod n$. Since each prime $p_j$ divides $n$, we have $a \equiv b \pmod{p_j}$ for every $j \in \{1, \ldots, k\}$. By the corresponding property of the [Legendre symbol](/theorems/???), $\left(\frac{a}{p_j}\right) = \left(\frac{b}{p_j}\right)$ for every $j$. Multiplying these equalities: \begin{align*} \left(\frac{a}{n}\right) &= \prod_{j=1}^{k} \left(\frac{a}{p_j}\right) = \prod_{j=1}^{k} \left(\frac{b}{p_j}\right) = \left(\frac{b}{n}\right). \end{align*} [/step] [step:Derive full multiplicativity (ii) from the Legendre case] For the multiplicativity in the upper argument, fix odd $n \geq 1$ and $a, b \in \mathbb{Z}$. The Legendre symbol is completely multiplicative in its upper argument (for each prime $p_j$, $\left(\frac{ab}{p_j}\right) = \left(\frac{a}{p_j}\right)\left(\frac{b}{p_j}\right)$ by the [multiplicativity of the Legendre symbol](/theorems/???)). Therefore \begin{align*} \left(\frac{ab}{n}\right) &= \prod_{j=1}^{k} \left(\frac{ab}{p_j}\right) = \prod_{j=1}^{k} \left(\frac{a}{p_j}\right)\left(\frac{b}{p_j}\right) = \left(\frac{a}{n}\right)\left(\frac{b}{n}\right). \end{align*} The multiplicativity in the lower argument, $\left(\frac{a}{mn}\right) = \left(\frac{a}{m}\right)\left(\frac{a}{n}\right)$, was recorded in the previous step. [/step] [step:Prove the parity identity $\frac{mn-1}{2} \equiv \frac{m-1}{2} + \frac{n-1}{2} \pmod 2$ for odd $m, n$] Let $m, n \geq 1$ be odd. Write $m = 2u + 1$ and $n = 2v + 1$ with $u, v \in \mathbb{Z}_{\geq 0}$. Then \begin{align*} mn &= (2u+1)(2v+1) = 4uv + 2u + 2v + 1, \end{align*} so $\frac{mn-1}{2} = 2uv + u + v$. Therefore \begin{align*} \frac{mn-1}{2} - \frac{m-1}{2} - \frac{n-1}{2} &= (2uv + u + v) - u - v = 2uv \equiv 0 \pmod 2. \end{align*} This yields the parity identity \begin{align*} \frac{mn-1}{2} &\equiv \frac{m-1}{2} + \frac{n-1}{2} \pmod 2, \end{align*} and, exponentiating $-1$, \begin{align*} (-1)^{(mn-1)/2} &= (-1)^{(m-1)/2} \cdot (-1)^{(n-1)/2}. \end{align*} [guided] The statement we want, (iii), asserts that the function $n \mapsto (-1)^{(n-1)/2}$ agrees with the Jacobi symbol $\left(\frac{-1}{n}\right)$ on odd $n \geq 1$. The Jacobi symbol is multiplicative in $n$ by definition. To lift the Legendre-level result ($\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}$ for odd primes $p$) to composite odd $n$, we must know that the right-hand side $(-1)^{(n-1)/2}$ is also multiplicative in $n$, which is precisely the parity identity established above. Why should $\frac{mn-1}{2} \equiv \frac{m-1}{2} + \frac{n-1}{2} \pmod 2$? The cleanest way is to write $m = 2u+1$, $n = 2v+1$ and compute $mn = 4uv + 2(u+v) + 1$, so $\frac{mn-1}{2} = 2uv + u + v$. The $2uv$ vanishes modulo $2$, leaving $u + v = \frac{m-1}{2} + \frac{n-1}{2}$. Alternative presentation: $(m-1)(n-1) = mn - m - n + 1 \equiv 0 \pmod 4$ because both factors are even; dividing by $2$ gives $\frac{mn-1}{2} - \frac{m-1}{2} - \frac{n-1}{2} \equiv 0 \pmod 2$. [/guided] [/step] [step:Deduce $\left(\frac{-1}{n}\right) = (-1)^{(n-1)/2}$ by induction on the number of prime factors] Factor $n = p_1 \cdots p_k$ as odd primes with multiplicity. By [Euler's criterion at odd primes](/theorems/???), for each odd prime $p_j$, \begin{align*} \left(\frac{-1}{p_j}\right) &= (-1)^{(p_j - 1)/2}. \end{align*} By definition of the Jacobi symbol, \begin{align*} \left(\frac{-1}{n}\right) &= \prod_{j=1}^{k} \left(\frac{-1}{p_j}\right) = \prod_{j=1}^{k} (-1)^{(p_j - 1)/2}. \end{align*} We now show by induction on $k$ that $\prod_{j=1}^{k} (-1)^{(p_j - 1)/2} = (-1)^{(n - 1)/2}$, where $n = p_1 \cdots p_k$. The base case $k = 1$ is immediate: both sides equal $(-1)^{(p_1 - 1)/2}$. For the inductive step, suppose the identity holds for products of $k-1$ odd primes. Let $n' = p_1 \cdots p_{k-1}$ and $n = n' p_k$; both $n'$ and $p_k$ are odd. By the inductive hypothesis, \begin{align*} \prod_{j=1}^{k-1} (-1)^{(p_j - 1)/2} &= (-1)^{(n' - 1)/2}. \end{align*} Multiplying by $(-1)^{(p_k - 1)/2}$ and applying the parity identity of Step 4 with $(m, n) = (n', p_k)$: \begin{align*} \prod_{j=1}^{k} (-1)^{(p_j - 1)/2} &= (-1)^{(n' - 1)/2} \cdot (-1)^{(p_k - 1)/2} = (-1)^{(n' p_k - 1)/2} = (-1)^{(n - 1)/2}. \end{align*} This proves (iii): \begin{align*} \left(\frac{-1}{n}\right) &= (-1)^{(n-1)/2}. \end{align*} [/step] [step:Prove the parity identity $\frac{m^2 n^2 - 1}{8} \equiv \frac{m^2 - 1}{8} + \frac{n^2 - 1}{8} \pmod 2$ for odd $m, n$] Let $m, n \geq 1$ be odd. For odd $x$, $x^2 \equiv 1 \pmod 8$: writing $x = 2t + 1$, we have $x^2 = 4t^2 + 4t + 1 = 4t(t+1) + 1$, and $t(t+1)$ is even (product of consecutive integers), so $8 \mid x^2 - 1$. In particular $\frac{m^2 - 1}{8}, \frac{n^2 - 1}{8}, \frac{m^2 n^2 - 1}{8} \in \mathbb{Z}$. We compute \begin{align*} m^2 n^2 - 1 &= (m^2 - 1)(n^2 - 1) + (m^2 - 1) + (n^2 - 1), \end{align*} which is verified by expanding the right-hand side: $(m^2 n^2 - m^2 - n^2 + 1) + (m^2 - 1) + (n^2 - 1) = m^2 n^2 - 1$. Dividing by $8$: \begin{align*} \frac{m^2 n^2 - 1}{8} &= \frac{(m^2 - 1)(n^2 - 1)}{8} + \frac{m^2 - 1}{8} + \frac{n^2 - 1}{8}. \end{align*} The first term on the right-hand side satisfies \begin{align*} \frac{(m^2 - 1)(n^2 - 1)}{8} &= 8 \cdot \frac{m^2 - 1}{8} \cdot \frac{n^2 - 1}{8} \equiv 0 \pmod 2, \end{align*} since $\frac{m^2 - 1}{8}, \frac{n^2 - 1}{8} \in \mathbb{Z}$ and the overall factor of $8$ makes the product divisible by $2$. Hence \begin{align*} \frac{m^2 n^2 - 1}{8} &\equiv \frac{m^2 - 1}{8} + \frac{n^2 - 1}{8} \pmod 2, \end{align*} and, exponentiating, \begin{align*} (-1)^{(m^2 n^2 - 1)/8} &= (-1)^{(m^2 - 1)/8} \cdot (-1)^{(n^2 - 1)/8}. \end{align*} [guided] The pattern exactly mirrors Step 4: we need the right-hand side of (iv), namely $(-1)^{(n^2 - 1)/8}$, to be multiplicative in odd $n$, so that the Legendre-level identity $\left(\frac{2}{p}\right) = (-1)^{(p^2 - 1)/8}$ can be lifted to composite $n$ via the defining multiplicativity of the Jacobi symbol. Why does this work? Because for odd $x$, $x^2 \equiv 1 \pmod 8$, so $\frac{x^2 - 1}{8}$ is a well-defined integer. The algebraic identity \begin{align*} m^2 n^2 - 1 &= (m^2 - 1)(n^2 - 1) + (m^2 - 1) + (n^2 - 1) \end{align*} is a rearrangement of $(m^2 - 1)(n^2 - 1) + (m^2 + n^2 - 2) = m^2 n^2 - m^2 - n^2 + 1 + m^2 + n^2 - 2 = m^2 n^2 - 1$. Dividing by $8$, the cross-term $\frac{(m^2 - 1)(n^2 - 1)}{8}$ is an even integer because both $\frac{m^2 - 1}{8}$ and $\frac{n^2 - 1}{8}$ are integers, and hence the product $(m^2 - 1)(n^2 - 1) = 64 \cdot \frac{m^2 - 1}{8} \cdot \frac{n^2 - 1}{8}$, which is divisible by $16$. Thus $\frac{(m^2 - 1)(n^2 - 1)}{8}$ is divisible by $2$, and it drops out modulo $2$. [/guided] [/step] [step:Deduce $\left(\frac{2}{n}\right) = (-1)^{(n^2 - 1)/8}$ by induction on the number of prime factors] Factor $n = p_1 \cdots p_k$ as odd primes with multiplicity. By the [Legendre symbol at $2$](/theorems/???), for each odd prime $p_j$, \begin{align*} \left(\frac{2}{p_j}\right) &= (-1)^{(p_j^2 - 1)/8}. \end{align*} By definition of the Jacobi symbol, \begin{align*} \left(\frac{2}{n}\right) &= \prod_{j=1}^{k} \left(\frac{2}{p_j}\right) = \prod_{j=1}^{k} (-1)^{(p_j^2 - 1)/8}. \end{align*} We prove by induction on $k$ that $\prod_{j=1}^{k} (-1)^{(p_j^2 - 1)/8} = (-1)^{(n^2 - 1)/8}$. The base case $k = 1$ is immediate. For the inductive step, let $n' = p_1 \cdots p_{k-1}$, so that $n = n' p_k$ with both factors odd. By the inductive hypothesis, $\prod_{j=1}^{k-1} (-1)^{(p_j^2 - 1)/8} = (-1)^{(n'^2 - 1)/8}$. Multiplying by $(-1)^{(p_k^2 - 1)/8}$ and applying the parity identity of Step 6 with $(m, n) \leftarrow (n', p_k)$: \begin{align*} \prod_{j=1}^{k} (-1)^{(p_j^2 - 1)/8} &= (-1)^{(n'^2 - 1)/8} \cdot (-1)^{(p_k^2 - 1)/8} = (-1)^{(n'^2 p_k^2 - 1)/8} = (-1)^{(n^2 - 1)/8}. \end{align*} This proves (iv): \begin{align*} \left(\frac{2}{n}\right) &= (-1)^{(n^2 - 1)/8}. \end{align*} [/step] [step:Combine the four parts] Parts (i) and (ii) were established in Steps 2 and 3 by transferring the Legendre-symbol identities through the defining product. Parts (iii) and (iv) were established in Steps 5 and 7 by combining the Legendre-level evaluations at $-1$ and $2$ with the parity identities of Steps 4 and 6. This completes the proof of all four properties of the Jacobi symbol. [/step]