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
    Yes I noticed that, but luckily I have proven that already. Thanks for your help mate.2012-11-18