MOE H3 Math Proofs and Reasoning Problem Set 1

MOE H3 Math Mathematical Proofs and Reasoning Problem Set 1 1. Determine whether each of the following statements is true or false? Give a direct proof if it is true, and give a counter-example if it is false. (a) The set of prime numbers is closed under addition. (b) The set of positive rational numbers is closed under division. 2. Let a, b and c be nonzero integers. Use the definition of divisibility and write down a direct proof for each of the following statements. (Indicate every step clearly.) (a) If a divides b, then ac divides bc. (b) If a divides b and b divides a, then a = ±b. 3. Show that 3 divides n(n + 1)(2n + 1) for any integer n. 4. Prove that for all integers a, if the remainder is NOT 2 when a is divided by 4, then 4 | a3 + 23a. 5. For any integer n >1, let the standard factored form of n be given by n = pk1 1 pk2 2 . . . pkr r . Prove that n is a perfect square if and only if k1, k2, . . . , kr are all even integers. 6. Prove the following bi-conditional statement: For all integers a and b, 3 | ab if and only if 3 | a or 3 | b. 7. Is the following statement true? If n(n + 1) 2 is odd, then so is (n + 1)(n + 2) 2 . 8. Let a, j, r, sbe fixed integers. Prove: if j divides r + s, then ∃ b ∈ Z (a = bj + r) ⇐ ⇒ ∃c ∈ Z (a = cj − s). 9. Prove that, if 3 ∤ a, then 3 | a2 + 5. 10. Prove the following statement: If m and n are any two integers with the same parity, then 4 | m2 − n2.

H3 Math (Mathematical Proofs and Reasoning) Problem Set 1 Hints 1. Hint for Question 3. Consider cases: n = 3k + r, r = 0, 1, 2. 2. Hint for Question 4. Consider cases: a = 4k + r, r = 0, 1, 3. 3. Hint for Question 5. For the “only if” part, may use the uniqueness of prime factor- ization. 4. Hint for Question 6. For the “only if” part, consider prove by contrapositive. 5. Hint for Question 9. Consider cases for a. Page 2