Question

Prove the following more general version of the Chinese Remainder Theorem: Theorem. Let m1, . . . , mN ∈ N, and let M = lcm(m1, . . . , mN ) be their least common multiple. Let a1, . . . , aN ∈ Z, and consider the system of simultaneous congruence equations    x ≡ a1 mod m1 . . . x ≡ aN mod mN This system is solvable for x ∈ Z if and only if gcd(mi , mj )| ai − aj for all i 6= j, and the solutions are precisely given by one congruence class x ≡ b mod M. Hint: Regarding existence: For x ≡ ai mod mi and x ≡ aj mod mj , argue by reducing further modulo gcd(mi , mj ) that gcd(mi , mj )| ai − aj is a necessary condition for existence. To prove sufficiency of this condition, first treat the case N = 2. In that case, reduce the problem by the prime factors of m1 and m2 and thereby consolidate to a single system of congruence equations with coprime moduli to which the standard Chinese Remainder Theorem can be applied. This establishes existence for N = 2. Then proceed to treat the general case N > 2 by induction with respect to N. At some point, you will probably have to apply the identity lcm(gcd(m1, mN+1), . . . , gcd(mN , mN+1)) = gcd(lcm(m1, . . . , mN ), mN+1) which is valid in view of Problem 2 (this identity can be proved based on Problem 2 by induction, but you may just use it in your proof).

Answer 1