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?
 A: 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.
A: 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).$$
