Results 1 to 3 of 3

Math Help - Chinese Remainder Theorem

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    11

    Chinese Remainder Theorem

    Hi,

    How would one approach solving equations using the CRT if n (the modulo) is not made of only primes.

    For example, n=63=3*3*7.

    And suppose 15x=12 mod 63.

    Under mod 3, clearly x = {0,1,2}
    and under mod 7, x=5

    So, to find a solution in mod 63,
    I started with x=0 mod 3.
    x=9t mod 3 for any t
    and also
    x = 5 mod 7,
    so 9t = 5 mod 7,
    so t=20=6+7s
    and so x=9*(7s + 6)=63s + 54.
    x mod 63 = 54.

    But 54 is not a solution.
    By brute force, the solution under mod 63 should be {5,26,47}
    Using what I did above for all three x values under mod 3 (i.e x={0,1,2}), I get x={54,19,47}.

    The only reason why I got one of them right is that it seems that those numbers that I get are multiples of 21 and 47 gives a multiple of 63.

    So I don't know how to go about this problem :S
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    To solve a congruence with modulus 63 by the CRT, you need to solve it mod 9 (not 3) and mod 7. But in cases like this, it's often quicker to cancel by a common factor first.

    The congruence 15x\equiv12\!\!\!\pmod{63} is equivalent to 5x\equiv4\!\!\!\pmod{21}. The reason for this is that if 15x+12=63k then you can divide by the common factor 3 to get 5x+4=21k.

    The congruence 5x\equiv4\!\!\!\pmod{21} has the solution x=5, and you get the solutions to the original congruence by adding multiples of 21.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    Posts
    120
    EDIT: Too slow. Same as ^
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 25th 2010, 08:56 PM
  2. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: July 31st 2009, 08:34 AM
  3. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 23rd 2009, 09:26 PM
  4. Chinese Remainder Theorem 1
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 26th 2007, 09:00 PM
  5. Chinese Remainder Theorem
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: November 17th 2006, 05:35 PM

Search Tags


/mathhelpforum @mathhelpforum