1
$\begingroup$

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 ?

1 Answers 1

1

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

  • 0
    "in the interval 1≤a≤a−1 " ? what do you mean here ?2012-11-18
  • 0
    A typo, sorry! It is the interval $1\le a\le n-1$. Corrected. Thanks.2012-11-18
  • 0
    Yes i thought so. Thank you ! This first solution is good for me :)2012-11-18
  • 0
    OK, but the second one is "better." Less computational, makes use of symmetry.2012-11-18
  • 0
    Yep. I will spent some time on this one tomorrow.2012-11-18
  • 0
    Just for clarification of solution 1. Let $A := \{1 \leq i \leq p-1 \mid i \in QR(p)\}$ and $B := \{1 \leq j \leq q-1 \mid j \in QR(q)\}$. Then for each par $(i,j) \in A \times B$ there exists (by the chinese remainder theorem) a uniqe $a$ with $1 \leq a \leq pq-1$ so that $a \equiv i \mod p$ and $a \equiv j \mod q$. But then (because $i\in A$ and $j \in B$) $a \in QR(p)$ and $a \in QR(q)$ such that $a \in QR(pq)$. There are $\frac{p-1}2 \frac{q-1}2$ elements in $A\times B$. Then we further got the same number elements with both $a \in NR(q)$ and $a \in NR(p)$. Is this correct ?2012-11-18
  • 0
    Yes, that is correct. I am using without proof the standard fact that for example there are $(p-1)/2$ QR of $p$ and $(p-1)/2$ NR.2012-11-18
  • 0
    Yes I noticed that, but luckily I have proven that already. Thanks for your help mate.2012-11-18