Compute QNR whose Jacobi is 1

Question

How do I compute a QNR in ZN which has a Jacobi of 1? N is product of distinct primes.

Answer 1

Let's assume $n=pq$ with different primes $p,q$. If $\left(\frac{a}{p}\right) = -1\;$ and $\left(\frac{a}{q}\right) = -1\;$ then $\left(\frac{a}{n}\right) = 1\,$ but $a$ is a QNR modulo $n$, because (Wiki):

This is because for a to be a residue (mod n) it has to be a residue modulo every prime that divides n, but the Jacobi symbol will equal one if for example a is a non-residue for exactly two of the primes which divide n.

So to get for example a QNR modulo 35 with $\left(\frac{a}{35}\right) = 1\;$ look for those $a$ which are simultaneously QNRs modulo 5 and 7. The first one is $a=3$ (by inspection you can find that there is no $x$ with $x^2 = 3 \pmod{35}$.