Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

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.

share|improve this answer
    
Could you give me some hints without using abstract algebra (homomorphism etc..)? –  CodeKingPlusPlus Nov 3 '12 at 23:28
add comment

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).$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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