# $N$ square-free $\Rightarrow \exists a \in (\mathbb Z / N\mathbb Z)^{\times}, (\frac{a}{N}) = -1$

I want to show that if $N$ is a square free odd integer then there is some number coprime to $N$ such that the Jacobi Symbol $(\frac{a}{N}) = -1$

Honestly I don't even know how to start showing this.

I know that for every odd prime $p$ there are $\frac{p-1}{2}$ quadratic residues$\pmod p$.

Taking the factorisation $N = p_1\dots p_k$ of distinct primes then, maybe I could argue that there's something that isn't a quadratic residue to an odd number of the prime factors. However, I can't quite see how I might manage something like that.

Hint: choose $a$ so that \begin{align*} a&\equiv1\pmod{p_1}\\ a&\equiv1\pmod{p_2}\\ &\cdots\\ a&\equiv1\pmod{p_{k-1}}\\ a&\equiv b\pmod{p_k} \end{align*} where $b$ is not a square modulo $p_k$.