If the given system has a solution, then
x≡b1 mod m1, x≡b2 mod m2,
therefore
x=b1+k1m1, x=b2+k2m2 for some integers k1 and k2
b1−b2=k2m2−k1m1
(m1,m2) divides m1 and m2 ⟹
b1−b2=k2l2(m1,m2)−k1l1(m1,m2) for some integers l1 and l2
b1−b2=(m1,m2)(k2l2−k1l1)
this means (m1,m2)∣b1−b2 .
\
If (m1,m2)∣b1−b2 ,then
b1−b2=k(m1,m2)
Using Bezout's identity
(m1,m2)=am1+bm2 for some integers a and b
b1−b2=k(am1+bm2)⟹
b1−kam1=b2+kbm2
Now, if we set x=b1−kam1=b2+kbm2, then x is the solution of the given congruence.
If x1 and x2 are two solutions of the given congruence, then
x1=b1+k1m1, x2=b2+k2m2⟹
x1−x2=b1−b2+k1m1−k2m2
(m1,m2) divides m1 and m2 and we proved that (m1,m2)∣(b1−b2), therefore
x1−x2 is divisible by (m1,m2)
and the solution is unique modulo (m1,m2).
\
x ≡ 3 mod 4
x ≡ 1 mod 6
3x ≡ 9 mod 12
2x ≡ 2 mod 12
3x-2x=x≡7 mod 12
x=7 is the solution of the given congruence.
Answer: x=7.
Comments