[proofplan] We factor the positive odd integer $n$ into odd prime powers and use the definition of the Jacobi symbol as the corresponding product of Legendre symbols. A solution modulo $n$ reduces to a solution modulo every prime divisor of $n$. Since $\gcd(a,n)=1$, each such prime does not divide $a$, so $a$ is a nonzero [quadratic residue](/page/Quadratic%20Residue) modulo that prime. Therefore every Legendre factor in the Jacobi product equals $1$, and hence the whole Jacobi symbol equals $1$. [/proofplan] [step:Factor $n$ and write the Jacobi symbol as a product of Legendre symbols] Since $n \geq 3$ is odd, its prime factorization has the form \begin{align*} n = \prod_{i=1}^{r} p_i^{e_i}, \end{align*} where $r \in \mathbb{N}$, the integers $p_1,\dots,p_r$ are distinct odd primes, and $e_1,\dots,e_r \in \mathbb{N}$. By the definition of the Jacobi symbol for positive odd denominators, \begin{align*} \left(\frac{a}{n}\right) = \prod_{i=1}^{r} \left(\frac{a}{p_i}\right)^{e_i}. \end{align*} Thus it is enough to prove that \begin{align*} \left(\frac{a}{p_i}\right)=1 \end{align*} for every $i \in \{1,\dots,r\}$. [/step] [step:Reduce the quadratic congruence modulo each prime divisor of $n$] By hypothesis, there exists $x \in \mathbb{Z}$ such that $x^2 \equiv a \pmod{n}$, meaning \begin{align*} n \mid x^2-a. \end{align*} Fix $i \in \{1,\dots,r\}$. Since $p_i \mid n$, divisibility is transitive, so \begin{align*} p_i \mid x^2-a. \end{align*} Equivalently, \begin{align*} x^2 \equiv a \pmod{p_i}. \end{align*} Also, $\gcd(a,n)=1$ and $p_i \mid n$ imply $p_i \nmid a$. Therefore $a$ is a nonzero quadratic residue modulo $p_i$. [guided] We now pass from the congruence modulo $n$ to congruences modulo the prime divisors of $n$. The hypothesis says that there is an integer $x$ satisfying \begin{align*} x^2 \equiv a \pmod{n}. \end{align*} By the definition of congruence modulo $n$, this means \begin{align*} n \mid x^2-a. \end{align*} Fix an index $i \in \{1,\dots,r\}$. From the factorization \begin{align*} n = \prod_{j=1}^{r} p_j^{e_j}, \end{align*} we know that $p_i \mid n$. Since $n \mid x^2-a$ and $p_i \mid n$, transitivity of divisibility gives \begin{align*} p_i \mid x^2-a. \end{align*} Converting this divisibility statement back into congruence notation gives \begin{align*} x^2 \equiv a \pmod{p_i}. \end{align*} We also need $a$ to be nonzero modulo $p_i$, because the Legendre symbol distinguishes nonzero quadratic residues from nonresidues. Since $\gcd(a,n)=1$, no prime divisor of $n$ divides $a$. In particular, \begin{align*} p_i \nmid a. \end{align*} Thus the residue class of $a$ modulo $p_i$ is nonzero, and the displayed congruence shows that it is a square modulo $p_i$. Hence $a$ is a nonzero quadratic residue modulo $p_i$. [/guided] [/step] [step:Evaluate every Legendre factor and multiply] For each $i \in \{1,\dots,r\}$, the previous step shows that $a$ is a nonzero quadratic residue modulo the odd prime $p_i$. By the definition of the Legendre symbol, \begin{align*} \left(\frac{a}{p_i}\right)=1. \end{align*} Substituting this into the Jacobi product gives \begin{align*} \left(\frac{a}{n}\right) = \prod_{i=1}^{r} \left(\frac{a}{p_i}\right)^{e_i} = \prod_{i=1}^{r} 1^{e_i} = 1. \end{align*} This proves the claimed necessary obstruction. [/step]