Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


share|cite|improve this question
@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
up vote 3 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.