Results 1 to 2 of 2

Math Help - System of Congruences

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    10

    System of Congruences

    Show that the system of congruences

    x== a1 mod(m1)
    x== a2 mod(m2)

    has a solution if and only if
    gcd(m1,m2) | (a1-a2)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,707
    Thanks
    1470
    Quote Originally Posted by justin6mathhelp View Post
    Show that the system of congruences

    x== a1 mod(m1)
    x== a2 mod(m2)

    has a solution if and only if
    gcd(m1,m2) | (a1-a2)
    x= a1 (mod m1) means x= a1+ pm1 for some integer p.
    x= a2 (mod m2) means x= a2+ qm2 for some integer q.

    Then a1+ pm1= a2+ qm2 so a1-a2= qm2- pm1.

    Let r= gcd(m1, m2). Then m1= ur and m2= us.
    Now we have a1- a2= q(ur)- p(us)= (qr- ps)u.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Is there a fast way to solve this system of congruences on paper?
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 19th 2010, 09:15 PM
  2. Trouble solving a system of linear congruences.
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 14th 2010, 10:10 AM
  3. CRT and System of Congruences
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 12th 2009, 10:08 PM
  4. Congruences
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: October 10th 2007, 07:59 PM
  5. Replies: 0
    Last Post: March 21st 2007, 09:18 AM

Search Tags


/mathhelpforum @mathhelpforum