1. ## Jacobian problem

The problem is

"Suppose n=pq where pq are distinct odd primes. prove that there always exist positive integers a,b, such that

$\left(\frac{a}{n}\right)=-1$ and $\left(\frac{b}{n}\right)=-1$, and such that $ab$ is not a square modulo n."

Does for ab to not be a square modulo n mean $\left(\frac{ab}{n}\right)=-1$?

I think I'm doing it wrong because I keep getting $\left(\frac{ab}{n}\right)=1$.

Could anyone give me a hand with this?

2. Well we always have $\left(\frac a n\right) \left(\frac b n\right)=\left(\frac {ab}{n}\right)$. So in this case, by assumption we have $\left(\frac {ab}{n} \right)=1$. You are asked to show that, although $\left(\frac {ab}{n} \right)=1$, $ab$ is not a square modulo $n$.

The point of the exercise is to realize that $\left(\frac {m}{n} \right)=-1$ implies that $ab$ is not a square, but that $\left(\frac {m}{n}\right)=1$ does not imply that $m$ is a square.

3. So since I keep getting $\left(\frac {ab}{n} \right)=1$, ab can be either a square not a square mod n. Do I use quadradic reciprocity to somehow find integers a and b so ab's not a square mod?

4. Here is why. Let $\mathbb{Z}_n,\mathbb{S}_n$ denote respectively the integers mod $n$ and the multiplicative group of nonzero squares mod $n$. We have

$S_n \cong \mathbb{Z}_n/\{\pm 1\}$

and also

$\mathbb{S}_{n} \cong \mathbb{S}_p \times \mathbb{S}_q$.

Therefore $|\mathbb{S}_{n}|=|\mathbb{S}_{p}||\mathbb{S}_{q}|= (p-1)(q-1)/4$. Since we have $\left(\frac{a}{n}\right)=1$ for $(p-1)(q-1)/2 = \phi(pq)/2$ elements $a$ of $\mathbb{Z}_n$, there must be some of those which are not elements of $\mathbb{S}_{n}$, i.e. not squares.