Statement:- If m 1 , m 2 , .., m k are pairwise relatively prime positive integers, and if a 1 , a 2 , .., a k are any integers, then the simultaneous congruences x ≡ a 1 (mod m 1 ), x ≡ a 2 (mod m 2 ), ..., x ≡ a k (mod m k ) have a solution, and the solution is unique modulo m, where M = m 1 m 2 ⋅⋅⋅ m k . Proof that a solution exists: To keep the notation simpler, we will assume k = 3. Note the proof is constructive, i.e., it shows us how to actually construct a solution. Our simultaneous congruence’s are x ≡ a 1 (mod m 1 ), x ≡ a 2 (mod m 2 ), x ≡ a 3 (mod m 3 ) We have to find integers w 1 ,w 2 ,w 3 such that x = a 1 w 1 + a 2 w 2 + a 3 w 3 . Moreover, as long as the moduli (m 1 , m 2 , m 3 ) remain the same, we can use the same w 1 , w 2 , w 3 with any a 1 , a 2 , a 3 . First define: z 1 = M / m 1 = m 2 m 3 z 2 = M / m 2 = m 1 m 3 z 3 = M / m 3 = m 1 m 2 Note that ...