Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $n := pq$ for $p,q$ odd primes. Denote $J_n^1 := \{a \in Z_n^* \mid J_n(a) = 1\}$ and $J_n^{-1} := \{a \in Z_n^* \mid J_n(a) = -1\}$. I want to show that $|J_n^1| = |J_n^{-1}|$ where $J_n(a)$ denotes the value of the jacobi-symbol. I already know that $a\in QR(n)$ iff $a \in QR(p)$ and $a \in QR(q)$.

I know that $J_n(a) = J_p(a)\cdot J_q(a)$. So i want to count elements which both are in $QR(p)$ and $QR(q)$ or not. That is $J_p(a)=J_q(a)$ and so $J_n(a) = 1$. How can i count these elements ?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

We give two solutions, the second much slicker than the first.

First way: Suppose that $1\le i\le p-1$ and $1\le j\le q-1$. By the Chinese Remainder Theorem, there is a unique $a$ in the interval $1\le a\le pq-1$ such that $a\equiv i \pmod{p}$ and $a\equiv j \pmod{q}$. Moreover, all $(p-1)(q-1)$ $a$'s in this interval that are relatively prime to $n$ arise in this way.

We get Jacobi symbol of $a$ is $1$ precisely if $i$ is a QR of $p$ and $j$ is a QR of $q$, or if $i$ is a NR of $p$ and $j$ is a NR of $q$. There are $\frac{p-1}{2}\cdot\frac{q-1}{2}$ of the first kind, and the same number of the second kind.

Essentially the same idea works for Jacobi symbol $-1$. However, it is faster to note that our answer for Jacobi symbol $1$ simplifies to $\frac{(p-1)(q-1)}{2}$, which is half of $\varphi(pq)$.

Second way: Without explicitly counting, one can show that in the interval $[1,pq-1]$ there are equal numbers of $a$ with Jacobi symbol $1$ and of $a$ with Jacobi symbol $-1$. That shows there are $\varphi(pq)/2$ of each kind.

The argument goes like this. There is a $c$ with Jacobi symbol $-1$. Look at all $x$ belonging to a reduced residue class modulo $pq$, say all numbers between $1$ and $pq$ relatively prime to $pq$. Consider all $cx$. These give us a reduced residue class modulo $pq$. But the mapping that takes $x$ to $cx$ transforms numbers with Jacobi symbol $1$ to numbers with Jacobi symbol $-1$, and vice-versa. So there must be equal numbers of each kind.

Remark: For the second way, we do need to show there is a $c$ with Jacobi symbol $-1$. For this, let $b$ be a quadratic non-residue of $p$, and use the Chinese Remainder Theorem to show there is a $c$ which is congruent to $b$ modulo $p$ and say to $1$ modulo $q$.

Note that if $p_1,p_2,\dots p_k$ are distinct odd primes, and $m$ is their product, the same argument shows that there are $\varphi(m)/2$ numbers in the interval $[1,m]$ that have Jacobi symbol modulo $m$ equal to $1$, and $\varphi(m)/2$ that have Jacobi symbol $-1$.

share|improve this answer
    
"in the interval 1≤a≤a−1 " ? what do you mean here ? –  André Nov 18 '12 at 22:19
    
A typo, sorry! It is the interval $1\le a\le n-1$. Corrected. Thanks. –  André Nicolas Nov 18 '12 at 22:27
    
Yes i thought so. Thank you ! This first solution is good for me :) –  André Nov 18 '12 at 22:30
    
OK, but the second one is "better." Less computational, makes use of symmetry. –  André Nicolas Nov 18 '12 at 22:32
    
Yep. I will spent some time on this one tomorrow. –  André Nov 18 '12 at 22:33

Your Answer

 
discard

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.