Number of solutions (equivalence classes) of congruence

[fleazo]

Homework Statement

How many solutions (equivalence classes) are there for the congruence 3x+11=20(mod12)

Homework Equations

a=b(modn) then for all c,
a+c=b+c(modn)
ac=bc(modn)

ab=ac(modn) then
b=c(modn) (if gcd(a,n)=1)
b=c(mod(n/d)) if gcd(a,n)=d > 1

The Attempt at a Solution

3x+11=20(mod12)
3x=9(mod12)
x=3(mod4) (because gcd(12,3)=4>1)

so solutions are x in the following set::

{...,-5,-1,3,7,11,...} (we can get these from the equation f(x)=4x+3)

The question is, how many equivalence classes are here? I can just test out [0],[1],[2],...,[11] hand by hand and find that [3], [7], and [11] represent all the possible solutions. But my question is, what's a faster way to do this? What theorem can I use that will tell me which equivalence classes are equal? (my initial thought was it would have to do with n and a being relatively prime, but 3 and 12 are not relatively prime and yet [3] is one of the equivalence classes so clearly I'm wrong there) Is this something like finding the "generators" of a cyclic group?

 

[Dick]

Mmm. Two equivalence classes [a] and are equal mod 12 if a-b is a multiple of 12. So if you have {...,-5,-1,3,7,11,...}, you just have to pick the ones that lie in range [0,11]. All of rest will differ from them by a multiple of 12. Or am I not getting what you are asking?