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?

  • $\begingroup$ 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$.) $\endgroup$ – 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.

  • $\begingroup$ Could you give me some hints without using abstract algebra (homomorphism etc..)? $\endgroup$ – 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).$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.