Prove the following more general version of the ChineseRemainder 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 congruenceequations    x ≡ a1 mod m1 . . . x ≡ aN mod mN This systemis solvable for x ∈ Z if and only if gcd(mi , mj )| ai − aj for alli 6= j, and the solutions are precisely given by one congruenceclass x ≡ b mod M. Hint: Regarding existence: For x ≡ ai mod mi andx ≡ aj mod mj , argue by reducing further modulo gcd(mi , mj ) thatgcd(mi , mj )| ai − aj is a necessary condition for existence. Toprove sufficiency of this condition, first treat the case N = 2. Inthat case, reduce the problem by the prime factors of m1 and m2 andthereby consolidate to a single system of congruence equations withcoprime moduli to which the standard Chinese Remainder Theorem canbe applied. This establishes existence for N = 2. Then proceed totreat the general case N > 2 by induction with respect to N. Atsome point, you will probably have to apply the identitylcm(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 beproved based on Problem 2 by induction, but you may just use it inyour proof).