Results 1 to 4 of 4

Math Help - Congruence classes

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    308

    Congruence classes

    For the linear congruence equation , the general solution is given by where is a particular solution and and .

    My book says for this general solution it forms 'd congruence classes mod n'. What does that mean?

    I interpreted it as this:

    is always a constant since so for some integer constant .

    So which can be written as which says ' congruence classes mod '

    There are congruence classes because so there are possible remainders, so there are congruence classes since there are possible remainders.

    How did they get 'd congruence classes mod n'?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by usagi_killer View Post
    For the linear congruence equation , the general solution is given by where is a particular solution and and .

    My book says for this general solution it forms 'd congruence classes mod n'. What does that mean?
    Suppose we restrict t to 0 \le t < d. It should be clear that these values of t will produce incongruent values mod n. Now suppose we let t = d. Then we have x = x_0 + n \equiv x_0\ (\text{mod}\ n). So.. d congruence classes mod n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2009
    Posts
    308
    Thanks but i still dont quite get it

    say we have the basic equation a = b mod n

    then a = nk+b where k is an integer.

    now since 0<=b<n we have b = {0,1,2,3,...,n-1} as possible remainders which means n possible remainders so that means n congruence classes.

    now applying this to the original Q

    if we are using mod n then we have x = x_0 + (t/d) n.

    now each congruence class represents a possible remainder, so 0=<x_0<n, so shouldn't there be n congruence classes?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by usagi_killer View Post
    Thanks but i still dont quite get it

    say we have the basic equation a = b mod n

    then a = nk+b where k is an integer.

    now since 0<=b<n we have b = {0,1,2,3,...,n-1} as possible remainders which means n possible remainders so that means n congruence classes.

    now applying this to the original Q

    if we are using mod n then we have x = x_0 + (t/d) n.

    now each congruence class represents a possible remainder, so 0=<x_0<n, so shouldn't there be n congruence classes?
    \displaystyle x_0 doesn't range over the integers, but rather \displaystyle t does.

    Let's take a concrete example. Say we want to solve \displaystyle 8x \equiv 16\ (\text{mod}\ 60). Obviously x=2 satisfies; we can use this as \displaystyle x_0. Now there are gcd(60,8)=4 distinct solutions mod 60. They are

    \displaystyle 2 + \frac{0\cdot60}{4} \equiv 2\ (\text{mod}\ 60)

    \displaystyle2 + \frac{1\cdot60}{4} \equiv 17\ (\text{mod}\ 60)

    \displaystyle2 + \frac{2\cdot60}{4} \equiv 32\ (\text{mod}\ 60)

    \displaystyle2 + \frac{3\cdot60}{4} \equiv 47\ (\text{mod}\ 60)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence Classes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 28th 2010, 10:34 AM
  2. Number of congruence classes
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: July 9th 2010, 01:27 AM
  3. Congruence classes and rings
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 26th 2010, 02:18 AM
  4. modulo and congruence classes
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: January 3rd 2008, 03:37 PM
  5. congruence classes
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: December 10th 2007, 07:02 AM

Search Tags


/mathhelpforum @mathhelpforum