# Congruence Classes and the Chinese Remainder Theorem

I am looking for some hints please!

Show that if $m = p_1\cdots p_r$ is a product of distinct odd primes, the set of odd $a$ such that

$\left(\dfrac{a}{m}\right) = 1$ are those lying in half of the congruence classes $b$ modulo $m$ such that $\gcd(b,m) = 1$.

Here is what I am thinking:

Want: odd $a_i$ for $i = 1$ to $\frac{m-1}{2}$ (half the congruences of $b \mod m$)

More explicitly I want:

$$b \equiv a_1 \mod m$$

$$b \equiv a_2 \mod m$$

$$\phantom{b\ \ }\vdots\phantom{\equiv a \mod m}$$

$$b \equiv a_{\frac{m-1}{2}} \mod m$$

Working backwards this could be written with the CRT as

$b \equiv a_i \mod p_i$

for $i = 1$ to $\frac{m-1}{2}$.

However, how could I get to this point and count the number of congruence classes that I have?

-
Hint: can you first prove it for $r = 1$, that is, for just one prime? (You need to prove that the quadratic residues $a$ modulo $p$ are exactly half of all nonzero numbers mod $p$.) –  ShreevatsaR Nov 3 '12 at 3:17

The congruence classes of numbers $\pmod m$ of numbers relatively prime to $m$ is a group under multiplication. All you really need is the multiplicative inverse of some $b,$ which is $bx \equiv 1 \pmod m,$ which is $bx - m y = 1$ in turn.

Then the Jacobi symbol is a group homomorphism to the set of two elements $\{1,-1 \}$ under multipliction. The kernel and the other coset are the same size.

Of course, you do need to show that both $1$ and $-1$ actually occur, so that the homomorphism is surjective.

-
Could you give me some hints without using abstract algebra (homomorphism etc..)? –  CodeKingPlusPlus Nov 3 '12 at 23:28

Hint: So you are working out properties of the Jacobi symbol.

The odd $a$ restriction, if I understand the problem, is no restriction at all. For the numbers in the interval $[1,m-1]$ that are relatively prime to $m$ are congruent, in some order, to the odd numbers in the interval $[1,2m-1]$ that are relatively prime to $m$.

So all we need to do is to show that the Jacobi symbol is equal to $1$ for half the integers in the interval $[1,m-1]$ that are relatively prime to $m$.

A natural approach is to try induction on $r$. The case $r=1$ is just the fact that if $p$ is an odd prime, then half of the numbers between $1$ and $p-1$ are quadratic residues of $p$, and half are non-residues.

For the induction step, use the following multiplicativity property of the Jacobi symbol. If $a$ and $b$ are relatively prime odd numbers, and $\gcd(x,a)=\gcd(x,b)=1$ then $$(x/a)(x/b)=(x/ab).$$

-