Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solving Systems of Congruences when mods not pairwise relatively prime

  1. Sep 25, 2011 #1
    Hi folks,

    The CRT says there's a unique solution to the system of congruences

    [itex] x = a [/itex] (mod m)
    [itex] x = b [/itex] (mod n)
    [itex] x = c [/itex] (mod p)

    in (mod mnp) when [itex] m, n, p [/itex] are pairwise relatively prime. But what if [itex] m, n, p [/itex] are NOT pairwise relatively prime. Is there a systematic way to solve these cases?
  2. jcsd
  3. Sep 27, 2011 #2
    The system may not have a solution if the moduli are not pairwise coprime.We can, of course,solve two equations at a time modulo the lcm & try to patch up the solutions... I don't know how to answer this best.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook