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+
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.
View Tag Cloud