Results 1 to 8 of 8

Math Help - Silly question probably..

  1. #1
    Newbie
    Joined
    Jun 2008
    Posts
    4

    Silly question probably..

    I have to solve a system using The Chinese Reminder Theorem.
    It has two equations:
    x= +-4 mod 31
    x= +- 22 mod 53
    I've got N = 1643 And a1N1K1 + a2N2K2 = +-5088+-8184.
    I know how to find the first two solutions:
    x1 = 5088 + 8184 (mod 1643)
    x2 = 8184 - 5088 (mod 1643)
    but how about x3, x4?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member bleesdan's Avatar
    Joined
    Jun 2008
    Posts
    37
    Could you please state the problem clearly?
    It's a little confusing right now.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,854
    Thanks
    321
    Awards
    1
    Quote Originally Posted by bleesdan View Post
    Could you please state the problem clearly?
    It's a little confusing right now.
    The problem statement is quite clear. See here.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by clarissa View Post
    I have to solve a system using The Chinese Reminder Theorem.
    It has two equations:
    x= +-4 mod 31
    x= +- 22 mod 53
    I've got N = 1643 And a1N1K1 + a2N2K2 = +-5088+-8184.
    I know how to find the first two solutions:
    x1 = 5088 + 8184 (mod 1643)
    x2 = 8184 - 5088 (mod 1643)
    but how about x3, x4?

    Thanks.
    Since the gcd of 31 and 53 is 1, there is only one solution (mod 1643). So there is no x3 and x4. In fact there cant be x1 and x2 too.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by clarissa View Post
    x= +-4 mod 31
    x= +- 22 mod 53
    .
    This is how I like to solve CR problems. Say we want to solve x\equiv 4 (\bmod 31) \mbox{ and }x\equiv 22(\bmod 53).

    If a is an integer then x\equiv 4(\bmod 31) if and only if x\equiv 4 + 31a(\bmod 31). Similarly if b is an integer then x\equiv 22(\bmod 53) if and only if x\equiv 22 + 53b(\bmod 53). We will find a,b such that 4+31a = 22+53b\implies 31a - 53b = 18. By using Euclidean algorithm we find a=216 and b=126. Which means x\equiv 22 + 53(126)(\bmod 53) \implies x \equiv 6700. And x\equiv 4+31(216)(\bmod 31)\implies x\equiv 6700(\bmod 31). Since \gcd(31,53)=1 it means x\equiv 6700 (\bmod 31\cdot 53)\implies x\equiv 6700 (\bmod 1643)\implies x\equiv 128(\bmod 1643).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,854
    Thanks
    321
    Awards
    1
    Now my question is this: The original problem statement has
    x \equiv \pm 4 \text{ (mod 31)}

    How can we even have this? The only number I can think of that can be equivalent to \pm 4 is 4 (mod 8).[/tex]

    -Dan
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by topsquark View Post
    Now my question is this: The original problem statement has
    x \equiv \pm 4 \text{ (mod 31)}

    How can we even have this? The only number I can think of that can be equivalent to \pm 4 is 4 (mod 8).[/tex]
    I think the person was doing two seperate problems. One involving + and one involving -.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,854
    Thanks
    321
    Awards
    1
    Quote Originally Posted by ThePerfectHacker View Post
    I think the person was doing two seperate problems. One involving + and one involving -.
    Heck, if I'd have thought of that, I could have answered the question.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Silly question...?!
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: December 21st 2010, 04:39 AM
  2. Silly question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 28th 2010, 01:33 AM
  3. A perhaps silly question about > 0
    Posted in the Calculus Forum
    Replies: 2
    Last Post: September 9th 2009, 08:09 AM
  4. A silly question
    Posted in the Calculus Forum
    Replies: 12
    Last Post: June 28th 2007, 06:06 AM
  5. Silly question
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 9th 2006, 11:25 AM

Search Tags


/mathhelpforum @mathhelpforum