 Solution

Factor $n={\prod }_j{q}_j^{e_j}$. Since it is not a square, one exponent, say $e_1$, is odd. Choose a nonzero quadratic nonresidue $a$ modulo $q_1$; one exists because the squaring map on the nonzero residues is two-to-one and hence has only $(q_1-1)/2$ images. The Chinese remainder theorem supplies a positive odd integer $m>1$ satisfyingThen $\gcd (m,n)=1$ and $(m/n)=(-1{)}^{e_1}=-1$. The Jacobi reciprocity law proved in part (i), together with $m\equiv 1(\mathrm{mod}4)$, gives $(n/m)=-1$. Factoring $m={\prod }_{\ell }{p}_{\ell }^{r_{\ell }}$ givesAll $p_{\ell }$ are odd and none divides $n$. At least one factor must be negative, yielding an odd prime number $\boxed{p\text{ with }(n/p)=-1}$. No theorem about primes in arithmetic progressions is needed.