= Solution
For positive odd coprime integers $m,n$, the <Jacobi reciprocity law> is
$$
\boxed{\left(\frac mn\right)\left(\frac nm\right)=(-1)^{(m-1)(n-1)/4}.}
$$
Factor $a=\prod_jq_j^{e_j}$. Since $a$ is not a square, some $e_j$ is <odd>. Choose a <quadratic nonresidue> modulo that $q_j$, and choose residue one modulo each other $q_i$. The <Chinese remainder theorem> provides a positive $n$ with these residues and with $n\equiv1\pmod4$. Multiplicativity of the <Jacobi symbol> then gives $(n/a)=-1$.
Suppose only finitely many <primes> $p_1,\ldots,p_s$ satisfy $(a/p_i)=-1$. They are coprime to $a$. Repeat the preceding <Chinese remainder theorem> construction, additionally imposing $n\equiv1\pmod{p_i}$ at every odd $p_i$ and taking $n\equiv1\pmod4$ to avoid two. Since $n\equiv1\pmod4$, <Jacobi reciprocity> gives $(a/n)=(n/a)=-1$. Factoring this <Jacobi symbol> over the prime factors of $n$ shows that at least one such prime $p$ has $(a/p)=-1$. But none of the listed primes divides $n$, a contradiction. This proves the <infinitely many prime quadratic nonresidues of a nonsquare integer> assertion.
Back to article page
