# Show that if we have a product of distinct odd primes m, then they lie in half of b modulo m.

I'm having a lot of difficultly understanding the approach I should use for this problem. I was wondering if anyone would be able to provide some assistance.

Show that if m = p1....pr 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 . As a corollary, deduce that for any odd integer n > 1, the primes p such that

$\left(\dfrac{n}{p}\right)$ = 1 are those in one of $\varphi(n)$ congruence classes of the $\varphi(2(n))$ congruence classes modulo 4n which can contain odd numbers.

-
You could try doing the first part by induction on $r$. –  Gerry Myerson Nov 2 '12 at 11:51