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)

Quote:

---

Originally Posted by justin6mathhelp

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.