Problem 2 (Chinese Remaindering Theorem) [20 marks/ Let m and n be two relatively prime integers. Let s,t E Z be such that sm +tn-1. The Chinese Remaindering Theorem states that for every a,b Z there exists c Z such that where a convenient c is given by 1. Prove that the above c satisfies both cEa mod m and cE b mod n. 2. Let x E Z. Prove that if x mod mn holds then x mod m and x b mod n both hold as well. 3. Let x Z. Prove that if both x a mo d m and c E b mod n hold then so does x c mod m n