Results 1 to 5 of 5

Math Help - Chinese remainder theorem problem

  1. #1
    Junior Member
    Joined
    Oct 2011
    Posts
    37

    Chinese remainder theorem problem

    Hi - I've come unstuck on a problem as I've not seen the like before:

     x\equiv 1\mod\17
     x\equiv 8\mod\15
     x\equiv 3\mod\35

    With out going into too much detail regarding the finer details of solving this I proceeed as moduli are all co-prime as required ( I thought that if this was the case then it is definately solveable!?). However, when looking at the last equation I'm trying to solve:

     10y\equiv 1\mod\35

    Here 10 and 35 are not co-prime so I cannot have an inverse or therefore solve it. If I rearrange the original equations to redefine  x\equiv 3\mod\35 I end up with contradictions in the question.

    How do I proceed? As mentioned, my understading is if the moduli are co-prime then an answer will always exist.

    Your help would be greatly received.

    BR, Felix
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,973
    Thanks
    1121

    Re: Chinese remainder theorem problem

    You "understanding" is not quite correct. If a system of modulus equation has co-prime moduli and each equation has a solution itself, then there exist values satifying all of them.
    However, here, because 10 and 35 have common factor, 5, there is NO x such that 10x is one more than a multiple of 35 there is no x satisfying the last equation alone and so cannot be a value of x satisfying all of them.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2011
    From
    Crna Gora
    Posts
    420
    Thanks
    64

    Re: Chinese remainder theorem problem

    solution must be congruent modulo the ~\operatorname{lcm} (15,17,35)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2011
    From
    Crna Gora
    Posts
    420
    Thanks
    64

    Re: Chinese remainder theorem problem

    Quote Originally Posted by HallsofIvy View Post
    You "understanding" is not quite correct. If a system of modulus equation has co-prime moduli and each equation has a solution itself, then there exist values satifying all of them.
    However, here, because 10 and 35 have common factor, 5, there is NO x such that 10x is one more than a multiple of 35 there is no x satisfying the last equation alone and so cannot be a value of x satisfying all of them.
    solution
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2010
    Posts
    906
    Thanks
    204

    Re: Chinese remainder theorem problem

    To be exact, the moduli have to be pairwise co-prime, so CRT doesn't work directly since 15 and 35 are not co-prime. But you can split up the second and third congruences:

    x\equiv{1}\mod{17}
    x\equiv{2}\mod{3}
    x\equiv{3}\mod{5}
    x\equiv{3}\mod{7}
    x\equiv{3}\mod{5}

    Since x\equiv{3}\mod{5} agrees, you still have solutions. If you got two different congruences, then of course you would have no solutions. So now you have four congruences:

    x\equiv{1}\mod{17}
    x\equiv{2}\mod{3}
    x\equiv{3}\mod{5}
    x\equiv{3}\mod{7}

    You will get a solution of the form x\equiv{x_0}\mod{N} where N=1785 is the LCM of the moduli.

    The first task is to find r_i and s_i such that r_im_i+s_i\frac{N}{m_i}=1. If the numbers were bigger, you would use the extended Euclidean algorithm, but here trial and error should do the job. For example, -37\cdot{17}+6\cdot{105}=1. So 6\cdot{105}=630 is congruent to 1 (mod 17), 0 (mod 3), 0 (mod 5), and 0 (mod 7).

    So you get 4 values for s_i\frac{N}{m_i}, multiply them by 1, 2, 3, and 3 and add them together to get the final solution, which will be congruent to the solution from princeps.

    - Hollywood
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Basic Chinese Remainder Theorem Problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 22nd 2010, 09:27 AM
  2. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 25th 2010, 07:56 PM
  3. Chinese Remainder Theorem Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 21st 2009, 01:49 PM
  4. Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 22nd 2009, 05:00 PM
  5. CRT(chinese remainder theorem)
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 19th 2009, 09:01 PM

Search Tags


/mathhelpforum @mathhelpforum