1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number of solutions (equivalence classes) of congruence

  1. Nov 1, 2012 #1
    1. The problem statement, all variables and given/known data

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

    2. Relevant 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


    3. 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?
     
  2. jcsd
  3. Nov 1, 2012 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Number of solutions (equivalence classes) of congruence
  1. Congruence Classes (Replies: 3)

  2. Equivalence Classes (Replies: 3)

Loading...