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

  • 0
    @DonAntonio: Try `\left(a\over b\right)` mate: $\left(a\over b\right)$.2012-06-27
  • 0
    Oh, dear: so easy and nice. Thanks @Anon2012-06-27
  • 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
    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$?2012-06-27
  • 0
    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$$2012-06-27
  • 0
    Oh silly me, it's basically the definition of it :)2012-06-27
  • 0
    Well, it *almost* is. We only need the little observation that if $\,\exists\,x\in\left(\mathbb Z/pq\mathbb Z\right)^*\,\,s.t.\,\,x^2=a\,\,$ then also $$x\pmod p\in\left(\mathbb Z/p\mathbb Z\right)^*\,\text{and}\,\,x^2=a\pmod p$$2012-06-27
  • 1
    @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})$?2012-06-27
  • 1
    @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! +12012-06-28
  • 0
    @DonAntonio I don't see a pure counting argument that produces such an $a$. The density of quadratic residues or non-residues mod $p$ is $\tfrac12 - \tfrac{1}{2p}$. Since $\tfrac12 - \tfrac{1}{2p} + \tfrac12 - \tfrac{1}{2q} < 1$, cardinality alone does not force the set of residues mod $q$ to overlap the set of non-residues mod $p$ (the problem is we need to exclude $0$). However, the Chinese remainder theorem produces $(p-1)(q-1)/4$ values of $a$ in $\left(\mathbb Z/pq\mathbb Z\right)^\times$.2012-06-28
  • 0
    @ErickWong, I added in my answer above an explanation that'll hopefully help to clear things.2012-06-29
  • 0
    @DonAntonio Thanks, looks quite good now! This also justifies KCd's comment about half of the remainders (even more when $n$ has more factors). One last nitpick for Jozef: the number $1$ is both squarefree and also a square, so the observation is for any odd squarefree _composite_ $n$.2012-06-29
  • 0
    Thank *you*, @ErickWong, as because of your comment I was forced to look closer to my first answer, which definitely was insufficient. About your last observation, Jozef made it clear that $\,n=pq\,$, with *distinct* odd primes $\,p,q\,$, so it is both composite and square free.2012-06-29
  • 0
    I got a little confuse here. Are you saying that for every $n=q_1q_2q_3..q_k$ you have at list $0.5 \phi(N)$ "a"s such that $a^{n-1/2} neq (\frac{a}{n})$? I didn't understand that. You showed only for $n=pq$.2012-06-29
  • 0
    Of course not, @Jozef ! The proof above was *only* for the case **you asked**, namely $\,n=pq\,\,,\,p,q\,$ odd primes. For other cases *perhaps* some generalization is possible but I can't say right now.2012-06-29
  • 0
    Okay thanks. I wanna ask you about your first comment to your answer. what if $n=pq$ and q is non- square residue as well? won't we get that it doesn't have to be always $-1$?2012-06-29
  • 0
    That comment, and my answer, prompted Erick's comments, which in turn prompted me to add what I did to my answer. Refer to this for what you need and see the comments only as anecdotical, though they show, thanks to Erick, how my first unedited answer was lacking and, in fact, incorrect (as it mainly referred to Legendre's symbol instead of its generalization, Jacobi's symbol.2012-06-29
  • 0
    Okay, Thanks. You're saying and "since any element in $(Z/nZ)∗$ is a square root", why is it true? I hope I don't bother you.2012-06-29
  • 0
    No bothering at all, @Jozef: for any $\,a\in\left(\mathbb Z/n\mathbb Z\right)^*\,\,,\,\,a\,$ is a square root of $\,a^2\,$...:)2012-06-30
  • 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