2
$\begingroup$

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

  • 1
    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.2012-06-27

1 Answers 1

3

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 . 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.

  • 0
    @DonAntonio: O.k, so I am convinced that there is$a$such that $(\frac{a}{q}) \neq (\frac{a}{p})$, but why does $a^{n-1/2}$ have to different form $-1$?2012-07-02