Congruence classes

Printable View

July 7th 2010, 07:51 PM
usagi_killer

Congruence classes

For the linear congruence equation http://stuff.daniel15.com/cgi-bin/ma...%5Cpmod%7Bn%7D, the general solution is given by http://stuff.daniel15.com/cgi-bin/ma...7Bnt%7D%7Bd%7D where http://stuff.daniel15.com/cgi-bin/mathtex.cgi?x_0 is a particular solution and http://stuff.daniel15.com/cgi-bin/ma...0=%20%28a,n%29 and http://stuff.daniel15.com/cgi-bin/ma...Cmathbb%7BZ%7D.

My book says for this general solution it forms 'd congruence classes mod n'. What does that mean?

I interpreted it as this:

http://stuff.daniel15.com/cgi-bin/ma...%7Bn%7D%7Bd%7D is always a constant since http://stuff.daniel15.com/cgi-bin/ma...cgi?n%20=%20kd so http://stuff.daniel15.com/cgi-bin/ma...7Bd%7D%20=%20k for some integer constant http://stuff.daniel15.com/cgi-bin/mathtex.cgi?k.

So http://stuff.daniel15.com/cgi-bin/ma...x%20=%20tk+x_0 which can be written as http://stuff.daniel15.com/cgi-bin/ma...%5Cpmod%7Bk%7D which says 'http://stuff.daniel15.com/cgi-bin/ma...%7Bn%7D%7Bd%7D congruence classes mod http://stuff.daniel15.com/cgi-bin/ma...%7Bn%7D%7Bd%7D'

There are http://stuff.daniel15.com/cgi-bin/ma...%7Bn%7D%7Bd%7D congruence classes because http://stuff.daniel15.com/cgi-bin/ma...0x_0%20%3C%20k so there are http://stuff.daniel15.com/cgi-bin/ma...ts%20k-1%5C%7D possible remainders, so there are http://stuff.daniel15.com/cgi-bin/mathtex.cgi?k congruence classes since there are http://stuff.daniel15.com/cgi-bin/mathtex.cgi?k possible remainders.

How did they get 'd congruence classes mod n'?
July 7th 2010, 08:00 PM
undefined

Quote:

Originally Posted by usagi_killer

For the linear congruence equation http://stuff.daniel15.com/cgi-bin/ma...%5Cpmod%7Bn%7D, the general solution is given by http://stuff.daniel15.com/cgi-bin/ma...7Bnt%7D%7Bd%7D where http://stuff.daniel15.com/cgi-bin/mathtex.cgi?x_0 is a particular solution and http://stuff.daniel15.com/cgi-bin/ma...0=%20%28a,n%29 and http://stuff.daniel15.com/cgi-bin/ma...Cmathbb%7BZ%7D.

My book says for this general solution it forms 'd congruence classes mod n'. What does that mean?

Suppose we restrict t to $0 \le t < d$ . It should be clear that these values of t will produce incongruent values mod n. Now suppose we let t = d. Then we have $x = x_0 + n \equiv x_0\ (\text{mod}\ n)$ . So.. d congruence classes mod n.
July 7th 2010, 11:00 PM
usagi_killer

Thanks but i still dont quite get it

say we have the basic equation a = b mod n

then a = nk+b where k is an integer.

now since 0<=b<n we have b = {0,1,2,3,...,n-1} as possible remainders which means n possible remainders so that means n congruence classes.

now applying this to the original Q

if we are using mod n then we have x = x_0 + (t/d) n.

now each congruence class represents a possible remainder, so 0=<x_0<n, so shouldn't there be n congruence classes?
July 7th 2010, 11:20 PM
undefined

Quote:

Originally Posted by usagi_killer

Thanks but i still dont quite get it

say we have the basic equation a = b mod n

then a = nk+b where k is an integer.

now since 0<=b<n we have b = {0,1,2,3,...,n-1} as possible remainders which means n possible remainders so that means n congruence classes.

now applying this to the original Q

if we are using mod n then we have x = x_0 + (t/d) n.

now each congruence class represents a possible remainder, so 0=<x_0<n, so shouldn't there be n congruence classes?

$\displaystyle x_0$ doesn't range over the integers, but rather $\displaystyle t$ does.

Let's take a concrete example. Say we want to solve $\displaystyle 8x \equiv 16\ (\text{mod}\ 60)$ . Obviously x=2 satisfies; we can use this as $\displaystyle x_0$ . Now there are gcd(60,8)=4 distinct solutions mod 60. They are

$\displaystyle 2 + \frac{0\cdot60}{4} \equiv 2\ (\text{mod}\ 60)$

$\displaystyle2 + \frac{1\cdot60}{4} \equiv 17\ (\text{mod}\ 60)$

$\displaystyle2 + \frac{2\cdot60}{4} \equiv 32\ (\text{mod}\ 60)$

$\displaystyle2 + \frac{3\cdot60}{4} \equiv 47\ (\text{mod}\ 60)$