Use Direct proof or contrapositive proof to solve and write in paper of each proofs. 1. If m, ne Z, then {xzZ:mn|x} C{xzZ:m|x} n {x=Z:n|x]. 2. If A, B and C are sets, then A U (Bn C) = (AUB) n (AUC). 3. If A and B are sets in a universal set U, An B whole bar = A bar U B bar. 4. If A, B and C are sets, then A*(B - C) = (A*B) - (A*C). 5. Let A and B be sets. Prove that ACB if and only if An B = A. 6 . Prove that {4k + 5:keZ) = (4k + 1:keZ) . 7. Prove that (Z*N) n (N*Z) = N*N. Each of the following statements is either true or false. If a statement is true, prove it. If a statement is false, disprove it. These exercises are cumulative, covering all topics addressed in Chapters 1-9. 8. For every natural number n, the integer 2n - 4n + 31 is prime. 9. If A, B, C and D are sets, then (A*B) n (C*D) = (An C)*(BnD). 10. If A and B are sets and An B = + then p(A) - p(B) Ep(A - B). 11. If A and B are finite sets, then |A U B| = [A| + |B|. 12 . There exists prime numbers p and q for which p - q = 1000. 13 . Suppose a, beZ . If alb and bla, then a = b.Prove the following statements with either induction, strong induction or proof by smallest counterexample. 14. Prove that 1 + 2" + 3- + 4 2 n(n + 1)(2n + 1) .. +n = for every positive integer n. 6 15. Prove that 3|(5 - 1) for every integer n 2 0