Number of solutions (equivalence classes) of congruence

  • Thread starter fleazo
  • Start date
  • #1
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?
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,263
619
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?
 

Related Threads on Number of solutions (equivalence classes) of congruence

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
0
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
1K
Replies
2
Views
2K
Top