Results 1 to 7 of 7

Math Help - CNT - Modulo

  1. #1
    Newbie
    Joined
    Nov 2007
    Posts
    21

    CNT - Modulo

    where '=' means 'congruent to'


    Solve both system of equations:


    1.
    x = 0 (mod 2)
    x = 0 (mod 3)
    x = 1 (mod 5)
    x = 6 (mod 7)

    Answer: x = ? (mod 210)


    2.
    x = 0 (mod 4)
    x = 1 (mod 9)
    x = 2 (mod 25)
    x = 3 (mod 49)

    Answer: x = ? (mod 44100)


    where '=' means 'congruent to'
    Last edited by AgentNXP; November 8th 2007 at 01:26 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2007
    Posts
    21
    Please!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by AgentNXP View Post
    Please!
    Just glancing at the first one, 6/2=0, 6/3=0, 6/5=1 remainder 1, 6/7 =0 remainder 6
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by SnipedYou View Post
    Hmm is this true?

    a \equiv b \pmod{m}
    a \equiv c \pmod{n}
    a \equiv b + c \pmod{m \cdot n}?
    No,

    For example a=5, b=9, c=12, m=4, n=7

    5 \equiv 9 \pmod{4} \Rightarrow \mbox{True}
    5 \equiv 12 \pmod{7} \Rightarrow \mbox{True}
    5 \equiv 21 \pmod{28} \Rightarrow \mbox{False}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1
    Quote Originally Posted by AgentNXP View Post
    1.
    x = 0 (mod 2)
    x = 0 (mod 3)
    x = 1 (mod 5)
    x = 6 (mod 7)

    Answer: x = ? (mod 210)
    See here.

    2, 3, 5, and 7 are pairwise coprime, so we may apply the Chinese Remainder theorem.

    To start the answer, as you mentioned, will be a modulo 2 x 3 x 5 x 7 = 210.

    We need to find a set of pairs of integers (r_i, s_i) such that
    2r_1 + \left ( \frac{210}{2} \right )s_1 = 1

    3r_2 + \left ( \frac{210}{3} \right )s_2 = 1

    5r_3 + \left ( \frac{210}{5} \right )s_3 = 1

    7r_4 + \left ( \frac{210}{7} \right )s_4 = 1

    As example solutions I get
    (r_1, s_1) = -51, 1)
    (r_2, s_2) = -23, 1)
    (r_3, s_3) = -25, 3)
    (r_4, s_4) = -17, 4)
    (Any solutions to these equations is acceptable.)

    So the solution to the system of equivalences is
    x = 0 \cdot \left ( \frac{210}{2} \right )s_1 + 0 \cdot \left ( \frac{210}{3} \right )s_2 + 1 \cdot \left ( \frac{210}{5} \right )s_3 + 6 \cdot \left ( \frac{210}{7} \right )s_4

    x \equiv 846 \bmod 210 = 6 \bmod 210

    You do the second one.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    I got 14752

    Thanks for post, topsquark, it was much easier to follow your example than my book's.

    I just wish I understood why this worked so that I wouldn't forget it again (it might be on my final, I'm taking discrete math right now)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member DivideBy0's Avatar
    Joined
    Mar 2007
    From
    Melbourne, Australia
    Posts
    432
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modulo
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 7th 2010, 05:14 PM
  2. Modulo help
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 18th 2010, 09:13 AM
  3. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 09:04 AM
  4. Modulo 42
    Posted in the Algebra Forum
    Replies: 3
    Last Post: June 2nd 2009, 05:00 PM
  5. Modulo
    Posted in the Algebra Forum
    Replies: 11
    Last Post: May 5th 2009, 02:24 PM

Search Tags


/mathhelpforum @mathhelpforum