I want to prove the following proposition:
Let $n=pq$ where $p,q$ are odd primes; Prove there exists a number $a \in \mathbb{Z}_n^x$ such that $a^\frac{n-1}{2} \neq (\frac{a}{n}) (\text{mod } n)$
I've tried assuming by contradiction that for each $a$ the two sides are equal, but it doesn't seem to help...
What can I do?
Assume, at first, that the primes are distinct.
Choose a non-square $\pmod p$, call it $n$. We can find an integer $N$ such that $$N\equiv n\pmod p\quad \& \quad N\equiv 1 \pmod q$$
Clearly we have $$\left( \frac Nn\right)=-1$$
Now consider $$N^{(n-1)/2}\pmod n$$ Suppose (counter to hypothesis) that this was $-1\pmod n$. Then we'd have $$N^{(n-1)/2}\equiv -1 \pmod n\implies N^{(n-1)/2}\equiv -1 \pmod q$$
But $N\equiv 1 \pmod q$ so the last congruence is absurd, hence we have a contradiction.
Note: We didn't need to make $N\equiv 1 \pmod q$, any square would have done as well. Therefore, this argument shows that there are quite a few examples $\pmod {pq}$. Indeed, half of the non-zero residues must be of the desired form (congruent to a square modulo one of the primes and a non-square modulo the other). Thus, at least half of the non-zero residues must be of the form you seek.
Finally: If $n=p^2$ then consider $N=p+1$. We remark that $$N^{(p^2-1)/2}\equiv \pm 1 \pmod n \implies N^{(p^2-1)}\equiv 1 \pmod n$$ Thus we get $$(1+p)^{p^2-1}\equiv 1 \pmod {p^2}\implies 1+(p^2-1)p\equiv 1 \pmod {p^2}\implies -p\equiv 0\pmod {p^2}$$ which is absurd.