1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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,

    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

    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


    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook