Results 1 to 9 of 9

Math Help - Chinese Remainder Theorem

  1. #1
    Member
    Joined
    Jul 2009
    Posts
    111
    Thanks
    1

    Lightbulb Chinese Remainder Theorem

    For the question,

    Find the smallest x which solves the system of congruence equations:

    x =+ 3 mod 15
    x =+ 6 mod 224, where =+ stands for congruence modulo operation.

    I gave an argument oriented solution as follows.

    Any multiple of 224 is even.
    So, 6+ any multiple of 224 is even.
    => x is even.

    Also, any multiple of 15 ends with 5 or 0.
    3+any multiple of 15 ends with 8 or 3.

    Since X is even, the number should end with 8.
    Since X = A number ending with 8,
    Also, X = A multiple of 224 + 6
    This means the multiple of 224 ends with 2.

    Checking the multiples of 224, we get 224, 448, 672.

    The smallest one is 672 ==> X is 678.

    This solves both the equations as 678 = 224*3 +6
    = 45*15 +3

    My friend argued about a general solution for the same problem using Chinese Remainder Theorem. I browsed results for the same in various sites.
    I find only a general solution found in most cases.

    Can anyone describe how to get the particular solution for this problem through Chinese Remainder Theorem?

    Also, please mention if there are any mistakes in my argument-oriented solution.
    Last edited by MAX09; July 27th 2009 at 07:42 PM. Reason: incorrect syntax
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jul 2009
    Posts
    192
    Thanks
    4
    yes you can....

    so we have

    3 mod 15
    6 mod 224

    gcd(224,15)=1 so we use chinese thm.

    first thing we need is integers a and b s.t...

    a15+b224=1

    and after we find a and b using euclid's algorithm we compute

    6a15+3b224 (mod 15.224=3360)

    euclid's algorithm gives a=15 and b=-1

    so 6(15)15+3(-1)224=678 mod 3360

    and adding and subtracting 3360 would give you many solutions.


    you can also use this method to solve many problems which your method would be increasingly difficult to use for example....

    Find a number which is 3 mod 7, 2 mod 5 and 1 mod 2.

    7,5 and 2 are coprime so use chinese thm...

    first concentrate on 3 mod 7 and 2 mod 5

    find a,b so that a7+b5=1

    a=-2 and b=3 using euclid

    compute 2a7+3b5 (mod 7.5=35)=2(-2)7+3(3)5=17 mod 35


    now do the same with 17 mod 35 and 1 mod 2

    i need to compute 1a35+17b2 where a35+b2=1

    a=1 and b=-17

    so 1a35+17b2=17 mod 70=87mod70


    Note: the reason why we need the gcd to be 1 is because the chinese remainder theorem is based on this.


    but you have a nice little argument there, nice one.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,396
    Thanks
    1846
    Here's a similar argument:

    x= 6 mod 224 so x= 224k+ 6 for some integer k. But 224= 14 mod 15 so that is the same as x= 14k+ 6 mod 15. We have x= 14k+ 6= 3 mod 15 or 14k= -3 mod 15 so 14k= 15j- 3 for some integer j. That is, 15j- 14k= 3. It is obvious that 15- 14= 1 (shortcutting the Euclidean division algorithm!) so 15(3)- 14(3)= 3. k= j= 3 is a solution. Taking k= 3, x= 224(3)+ 6= 678.

    But if you can come up with a valid argument of your own, that's always best.
    Last edited by HallsofIvy; July 28th 2009 at 08:35 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jul 2009
    Posts
    111
    Thanks
    1
    @Krahl
    Thanks for your descriptive reply for the question; I get the solution part right till the general solution; You had mentioned that adding and subtracting 3360 would yield other solutions; It is this part where I do mistakes some times.

    Can you please throw some more light on one or two of the particular solutions?



    MAX,
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jul 2009
    Posts
    111
    Thanks
    1
    @HallsofIvy

    That's another interesting aliter for the same problem; Good one
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517

    CRT

    I was just thinking it might actually help you to see the actual proof of the theorem so you can see why these solution methods actually work. I am not sure if you are familiar with rings and ideals and stuff, so I will leave it in terms of the integers, but if you are interested, the same proof idea works in general.

    You assume that (m,n)=1 (this is enough to show in a ring (m)+(n)=R).
    Then you have the following isomorphism:
    \frac{\mathbb{Z}}{mn\mathbb{Z}}\cong \frac{\mathbb{Z}}{m\mathbb{Z}} \times \frac{\mathbb{Z}}{n\mathbb{Z}}

    Here is the isomorphism:
    \phi(x)=(x (mod m), x (mod n)).
    It is a homomorphism:
    \phi(x+y)=(x+y (mod m), x+y (mod n)) =(x (mod m), x (mod n)) +(y (mod m), y (mod n))= \phi(x)+\phi(y).

    It is pretty clear that ker(\phi)=mn\mathbb{Z}

    So it remains to show that it is surjective, and this is the key part of the argument for what you are looking for.

    Let (a (mod m), b (mod n)) be an arbitrary element of \frac{\mathbb{Z}}{m\mathbb{Z}} \times \frac{\mathbb{Z}}{n\mathbb{Z}}

    This is basically saying we need some integer that will satisfy
    x\equiv a (mod m) and
    x\equiv b (mod n).

    So this is the trick. Because we know (m, n) by the euclidean algorithm, there exists s,t \in \mathbb{Z} such that sm+tn=1.

    Just a side note: In the more general setting you say that the ring contains a unit and since we have (m)+(n)=R, there exists i\in (m) and j\in (n) such that i +j =1. Actually the ring need not even be a PID, it is true for any ideals that are comaximal in a commutative ring.

    So back to the surjectivity. We want to sort of cross multiply here and take the value bsm+atn and see that it maps where we want it.

    \phi(bsm+atn)=(bsm+atn (mod m), bsm+atn (mod n)) =(atn (mod m), bsm (mod n))= (a(1-sm) (mod m), b(1-tn) (mod n))= (a-asm) (mod m), b-btn (mod n))= (a) (mod m), b (mod n)).

    So this proves the isomorphism. This shows you bsm+atn (mod mn) is the number you want to pick to solve the system of equations above.

    The fact that the kernel is mn\mathbb{Z} just tells you that you can actually just add kmn for any integer k to your solution and you will get all the solutions to this system of equations.

    Hope this was helpful.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jul 2009
    Posts
    192
    Thanks
    4
    Quote Originally Posted by MAX09 View Post
    @Krahl
    Thanks for your descriptive reply for the question; I get the solution part right till the general solution; You had mentioned that adding and subtracting 3360 would yield other solutions; It is this part where I do mistakes some times.

    Can you please throw some more light on one or two of the particular solutions?



    MAX,
    Hi max

    not sure what part of the solution you're asking for but i'll try writing a few things on the solutions.

    well you agree that 678 is a solution right?

    Now the useful thing about using the chinese rem thm is that you end up not just with the answer 678 but also mod 3360.

    This mean that any number which is modulo 3360 would satisfy your equations,

    for example if we add and subtract 3360 we get the following alternative solutions;

    ........, -2682,678,4038,7398.......,

    Now this means that all these numbers are 678 modulo 3360
    i.e. have remainder 678 when divided by 3360.

    so 4038=3360+678, 7398=3360*2+678 etc...

    And the theorem claims that all these solutions also satisfy, so let's check them;


    7398=15*493+3 so it is 3 mod 15

    7398=224*33+6 so it is 6 mod 224

    That is why the question asks for the smallest positive solution.

    I did the same with the other example and got the solutions 17 mod 70 and 87 mod 70.

    Also notice this step i did;

    6a15+3b224


    its 6 mod 224 that is why 6 is next to 15. since 224 = 0 mod 224 so that you are left with 6a15 + 0 mod224

    and so a*15 must give me 1 mod 224 so that
    6a15+0 mod 224=6 mod 224

    and same with mod 15.

    any problems dont hesitate to post
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jul 2009
    Posts
    111
    Thanks
    1
    @Gamma

    That wasn't exactly the procedure I was looking for. Anyways, thanks for the effort.. It helped understanding the relation the CRT had with isomorphisms. Thanks a bunch !!!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jul 2009
    Posts
    111
    Thanks
    1

    Thumbs up @krahl

    Yes, your posted help me understand the procedure completely I had to get my basics on the Extended Euclidean Algorithm right. The following url helped me.

    http://marauder.millersville.edu/~bikenaga/absalg/euc/euclidex.html

    Thanks again, Krahl!!

    Max
    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: 1
    Last Post: March 23rd 2009, 09:26 PM
  3. Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 1st 2008, 02:27 AM
  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