Question on application of Chinese Remainder Theorem x ≡ 3 ( mod 30 ) x ≡ 5 ( mod 56 ) I have a system of modular equation that I want to solve. However, I thought that this system has no solution because the modulos are not coprime. Further, attempting to solve using chinese remainder theorem: x ≡ 56 p + 30 qwhere p is such that 56 p ≡ 3 ( mod 30 ) and q is such that 30 q ≡ 5 ( mod 56 ) However, again the modular inverses of these do not exist.Yet, one solution to this system of modular inequalities is 1293. How come the Chinese remainder theorem gives that no solution exists?

Question

Question on application of Chinese Remainder Theorem  x    ≡    3        (          mod            30    )    x    ≡    5        (          mod            56    )  I have a system of modular equation that I want to solve. However, I thought that this system has no solution because the modulos are not coprime. Further, attempting to solve using chinese remainder theorem:  x    ≡    56  p    +    30  qwhere   p is such that  56  p    ≡    3        (          mod            30    )    and   q is such that  30  q    ≡    5        (          mod            56    )    However, again the modular inverses of these do not exist.Yet, one solution to this system of modular inequalities is 1293. How come the Chinese remainder theorem gives that no solution exists?

Govorei9b · Accepted Answer

Better if you write it as  x  ≡  3    (  mod    2  )  ,  x  ≡  3    (  mod    15  )  ,  x  ≡  5    (  mod    8  )  ,  x  ≡  5    (  mod    7  )  .The ones with 2 and 8 are consistent, as the one with 2 is just asking for an odd number, so the system is equivalent to  x  ≡  3    (  mod    15  )  ,  x  ≡  5    (  mod    8  )  ,  x  ≡  5    (  mod    7  )  ,where now the moduli are coprime. That is the requirement for the Chinese Remainder Theorem.So we combine second and third again to get  x  ≡  3    (  mod    15  )  ,  x  ≡  5    (  mod    56  )  .For the 56 one, we have  5  ,  61  ,  117  ,  173  ,  229  ,  285  ,  341  ,  397  ,  453  ,  …and  453  ≡  3    (  mod    15  )  .

Question on application of Chinese Remainder Theorem x <mspace width="thickmathspace" />

Answered question

Answer & Explanation

New Questions in Algebra I