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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Solving Systems of Congruences when mods not pairwise relatively prime
  1. Prime & Congruences (Replies: 7)

  2. Congruences and primes (Replies: 2)

  3. Congruence Solving (Replies: 6)

Loading...