Thread: Congruence classes

For the linear congruence equation , the general solution is given by where is a particular solution and and .

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

I interpreted it as this:

is always a constant since so for some integer constant .

So which can be written as which says ' congruence classes mod '

There are congruence classes because so there are possible remainders, so there are congruence classes since there are possible remainders.

How did they get 'd congruence classes mod n'?

Originally Posted by usagi_killer

For the linear congruence equation , the general solution is given by where is a particular solution and and .

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

Suppose we restrict t to . It should be clear that these values of t will produce incongruent values mod n. Now suppose we let t = d. Then we have . So.. d congruence classes mod n.

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?

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?

doesn't range over the integers, but rather does.

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