I've been doing a few number theory problems online for fun and I've been having a bit of trouble with proving this one successfully:
Suppose $p$ and $q$ are distinct odd primes. Prove that there is always some integer $n$ with $(n / pq) = -1$ (where $(n / m)$ means the Jacobi symbol of $n$ and $m$).
I ended up with $(p/n)(q/n)$ and tried using the prime factorization of n to try to get somewhere, but I don't think it's the correct path. I think what I need to do is prove that there is always some n that can be a quadratic non-residue modulo pq. However, I've also been having a bit of trouble trying to prove this.
Could someone give a bit of guidance to help me out? Thanks.
You don't need to deal with the prime factorization of $n$, apart from it being relatively prime to $pq$, but that is implicit in the equation you have. Also, instead of "$(p/n)(q/n)$", your symbols should be the reciprocal of this. In particular, rewriting your equation of Jacobi symbols in terms of Legendre symbols gives
$$\left(\frac{n}{pq}\right) = \left(\frac{n}{p}\right)\left(\frac{n}{q}\right) = -1 \tag{1}\label{eq1A}$$
This means one of the Legendre symbol values is $1$ and the other is $-1$. Since $p$ and $q$ are odd primes, there's always at least one quadratic residue and one quadratic non-residue for each. Assume the first Legendre symbol value is $1$, so let $x$ be a quadratic residue modulo $p$, and the second one is $-1$, so let $y$ be a non-quadratic residue modulo $q$. You thus have the following $2$ congruence equations to solve for $n$:
$$n \equiv x \pmod p \tag{2}\label{eq2A}$$
$$n \equiv y \pmod q \tag{3}\label{eq3A}$$
Since $\gcd(p,q) = 1$, the Chinese remainder theorem states you can solve the above $2$ equations to get a unique solution of $n$ modulo $pq$.