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

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

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

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

Could anyone give me a hand with this?

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

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

3. So since I keep getting $\displaystyle \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 $\displaystyle \mathbb{Z}_n,\mathbb{S}_n$ denote respectively the integers mod $\displaystyle n$ and the multiplicative group of nonzero squares mod $\displaystyle n$. We have

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

and also

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

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