1
$\begingroup$

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?

  • 0
    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$.)2012-11-03

2 Answers 2