# Showing for $n=pq$, s.t $p,q$ primes, there is $a$ mod $(\bmod n)$ s.t. $a^{(n-1)/2} \neq (\frac{a}{n})$, where $(\frac{a}{n})$ is a Jacobi symbol

I'd really love your help with the following question:

For $n= pq$, where $p, q$ are both distinct odd prime numbers. I need to show that there is unit $a$ modulo $n$ such that $a^{(n-1)/2} \not\equiv (\frac{a}{n}) \bmod n$, where $\left(a\over n\right)$ is a Jacobi symbol.

I chose $a \equiv 1 (\bmod p)$ so we get that $a^{(q-1)/2} \equiv 1 (\bmod p)$ since $(q-1)/2$ is a positive integer. I feel it should follow from here that $a^{(q-1)/2} \equiv \left(a\over q\right)\equiv -1 (\bmod q)$, but I can't prove it to myself, why would it be correct? I'm missing something. With this I get that $\left(a\over n\right)\equiv -1 (\bmod q)$, and I am done, since $a=a^{(n-1)/2}=1 (\bmod q)$ so I get that $a^{(n-1)/2} \neq \left(a\over n\right) (\bmod q)$ and also for $\bmod n$ since $p|n$.

Thanks

-
@DonAntonio: Try \left(a\over b\right) mate: $\left(a\over b\right)$. –  anon Jun 27 '12 at 11:11
Oh, dear: so easy and nice. Thanks @Anon –  DonAntonio Jun 27 '12 at 11:16
This is a special case of the general fact that for any composite integer $n$ there is an $a \bmod n$ (in fact, at least half of all $a \bmod n$) such that $a^{(n-1)/2} \not\equiv (\frac{a}{n}) \bmod n$. Google Solovay-Strassen test or Euler-Jacobi pseudoprime. –  KCd Jun 27 '12 at 21:09
add comment

## 1 Answer

Take $\,p=3\,,\,q=5\,,\,a=4=1\pmod 3\,$ , then $$a^{\frac{q-1}{2}}=16=\left\{\begin{array}{} 1 \pmod 3\\1\pmod 5\end{array}\right.=1\pmod{15}$$so what you "you feel" it is implied is just not true.

Nevertheless, and following your argument, we see we need in element $\,a\in\left(\mathbb Z/pq\mathbb Z\right)^*\,$ as $\,a\,$ that you described, but it won't be that trivially easy found...so it won't be that hard to find, either.

What didn't work with the above example? That we chose an element that was both a square modulo $\,p\,$ and modulo $\,q\,$, so we must avoid this.

So assume $\,p<q\,$ . Since there are $\,\displaystyle{\frac{r-1}{2}}\,$ non-zero squares modulo any prime $\,r\,$, we see we can always choose and element $\,a\,$ s.t. $$\left(a\over p\right)=-\left(a\over q\right)$$

In the example above, $\,2\,$ works: $$2^{\frac{15-1}{2}}=\left(2^4\right)2^3=1\cdot 2^3=8\neq -1=\left(2\over {15}\right)$$

Hopefully the above is what you meant and this will help you.

Added This addition comes trying to address Erick's comments below.

As already said, for any prime $\,r\,$ there are exactly $\,\displaystyle{\frac{r-1}{2}}\,$ non-zero quadratic residues modulo $\,r\,$, which is exactly half of the non-zero elements of the field $\,\mathbb F_r:=\mathbb Z/r\mathbb Z\,$.

Now, for $\,a\in\mathbb Z/n\mathbb Z\,\,,\,\,n=pq\,$ , we have $$1=\left(a\over pq\right)=\left(a\over p\right)\left(a\over q\right)\Longrightarrow$$either $\,a\,$ is a quadratic residue modulo both $\,p\,,\,q\,$ or else it is a non-quadratic residue modulo both $\,p\,,\,q\,$ .

In particular, if $\,a\,$ is a quadratic residue modulo $\,n\,$, then it must be a quadratic residue modulo both $\,p\,,\,q\,$ . As any quadratic residue modulo a prime has two different square roots, we get that any quadratic res. modulo $\,n\,$ has 4 different roots (this is easily obtained applying the Chinese Remainder Theorem), and since any element in $\,\left(\mathbb Z/n\mathbb Z\right)^*\,$ is a square root of some element, if we denote the set of quadratic res. modulo $\,n\,$ by $\,Q_n\,$, we get $$|Q_n|=\frac{\left|\left(\mathbb Z/n\mathbb Z\right)^*\right|}{4}=\frac{(p-1)(q-1)}{4}$$

We want to prove the existence of an element $\,a\in\left(\mathbb Z/n\mathbb Z\right)^*\,$ s.t. $\,\displaystyle{\left(a\over p\right)=-\left(a\over q\right)}\,$ , but if we put $$NQ_n:=\left\{b\in \left(\mathbb Z/n\mathbb Z\right)^*\;\;;\;\;\left(b\over p\right)=\left(b\over q\right)=-1\right\}$$ this follows from the fact that $$|Q_n|=|NQ_n|$$ as there's the same number of quadratic and non-quadratic res. modulo a prime, so we're left with $$\frac{\left|\left(\mathbb Z/n\mathbb Z\right)^*\right|}{2}$$elements that are either quadratic residues modulo $\,p\,$ or modulo $\,q\,$ but not both, and any of these will do.

Please do not hesitate to make any comment if you see any mistake or "weird" thing above.

-
Thank you for the answer. Does it always true that for every odd square-free $n$ there's $a$ such that $(\frac{a}{n})=-1$? –  Jozef Jun 27 '12 at 13:56
You're welcome, @Jozef, and yes: just let $\,p\,$ be any prime dividing $\,n\,$ and let $$a\in\left(\mathbb Z/p\mathbb Z\right)^*\,\,\text{be a non-square residue}\,\Longrightarrow \left(a\over n\right)=-1$$ –  DonAntonio Jun 27 '12 at 14:06
Oh silly me, it's basically the definition of it :) –  Jozef Jun 27 '12 at 14:18
@DonAntonio Are you sure your construction in the comments is for the Jacobi symbol $(\tfrac{a}{n})$ and not the Legendre symbol $(\tfrac{a}{n})$? –  Erick Wong Jun 27 '12 at 22:43
@ErickWong, you're right: I completely forgot about the Jacobi symbol when I tried to address Jozef's comments! But taking the Jacobi symbol as a product of Legendre symbols, we get $$-1=\left(a\over n\right)=\left(a\over p\right)\left(a\over q\right)\Longleftrightarrow$$ with $\,a\,$ is a square modulo $\,p\,$ and a non-square modulo $\,q\,$ or the other way around. Then we can use the argument given in my answer, because there are more squares modulo the greatest prime, so we can choose one of these that won't be a square when reduced the smaller prime. Thanks a lot for your comment! +1 –  DonAntonio Jun 28 '12 at 1:51
show 12 more comments