- #1

fleazo

- 81

- 0

## 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?