MOE H3 Math Proofs and Reasoning Problem Set 1 Solutions

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. Solution: False. Counter-example: a = 3, b= 5 but a + b = 3 + 5 = 8 which is not a prime. (b) The set of positive rational numbers is closed under division. Solution: True. Direct proof: Suppose a and b are positive rational numbers. Then there exists positive integers m, n, p, qsuch that a = m n and b = p q . Then a ÷ b = m n ÷ p q = mq np . Since mq and np are positive integers, so a ÷ b is a positive rational number. Hence 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. Solution: Suppose a | b. (Starting with hypothesis) There exists an integer d such that b = ad. (Definition of divisibility) By multiplying c on both sides, we have bc = (ad)c = d(ac). (Algebraic manipula- tion) This means ac | bc. (Definition of divisibility- conclusion) (b) If a divides b and b divides a, then a = ±b. Solution: Suppose a | b and b | a. (Starting with hypothesis) There exist integers c and d such that b = ac and a = bd. (Definition of divisibility) So b = ac = (bd)c = b(cd). Thus cd = 1. (Algebraic manipulation) This implies c, dare divisors of 1, (Definition of divisibility) and hence c, d= ±1 (by a proved theorem) This means a = ±b. (Conclusion) 3. Show that 3 divides n(n + 1)(2n + 1) for any integer n. Solution: We consider three cases: Case (i) n = 3k for some integer k: so n(n + 1)(2n + 1) = 3k(n + 1)(2n + 1), which is divisible by 3.

H3 Math (Mathematical Proofs and Reasoning) Problem Set 1 Case (ii) n = 3k + 1 for some integer k: so n(n + 1)(2n + 1) = n(n + 1)(2[3k + 1] + 1) = n(n + 1)(6k + 3) = 3n(n + 1)(2k + 1), which is divisible by 3. Case (iii) n = 3k + 2 for some integer k: so n(n + 1)(2n + 1) = n([3k + 2] + 1)(2n + 1) = n(3k + 3)(2n + 1) = 3n(k + 1)(2n + 1), which is divisible by 3. We see that, for all the three cases, n(n + 1)(2n + 1) is divisible by 3. 4. Prove that for all integers a, if the remainder is NOT 2 when a is divided by 4, then 4 | a3 + 23a. Solution: Since a ̸= 4k + 2 for any integer k, we have three cases: Case (i) a = 4k a3 + 23a = (4k)3 + 23(4k) = 4[16k3 + 23k] which is divisible by 4. Case (ii) a = 4k + 1 a3 + 23a = (4k + 1)3 + 23(4k + 1) = 4[16k3 + 12k2 + 26k + 6] which is divisible by 4. Case (iii) a = 4k + 3 a3 + 23a = (4k + 3)3 + 23(4k + 3) = 4[16k3 + 36k2 + 50k + 24] which is divisible by 4. We see that, for all three cases, 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. Solution: (⇐) Suppose k1, k2, . . . , kr are all even integers. We can write ki = 2hi for some integer hi. Then n = p2h1 1 p2h2 2 . . . p2hr r = (ph1 1 ph2 2 . . . phr r )2. Let m = ph1 1 ph2 2 . . . phr r , which is an integer. So we have n = m2, which is a perfect square. Page 2

H3 Math (Mathematical Proofs and Reasoning) Problem Set 1 (⇒) Suppose n is a perfect square. We can write n = m2 for some integer m. Since n >1, we have m >1, and since m is a divisor of n, it has a standard factored form m = ph1 1 ph2 2 . . . phr r where 0 ≤ hi ≤ ki. Then n = (ph1 1 ph2 2 . . . phr r )2 = p2h1 1 p2h2 2 . . . p2hr r . By comparing with the standard factored form of n and the uniqueness of prime factorization, the prime power ki = 2hi for all i. In other words, ki are all even. 6. Prove the following bi-conditional statement: For all integers a and b, 3 | ab if and only if 3 | a or 3 | b. Solution: (⇐) We are supposed to prove two cases: (i) If 3 | a then 3 | ab; and (ii) If 3 | b then 3 | ab. Without loss of generality, we just need to prove one case. (Notice by interchanging a and b, it will not change the statement.) So suppose 3 | a. Then a = 3k for some integer k. Then ab = 3kb would imply 3 | ab. This proved the ‘If’ part. (⇒) We prove this by contrapositive. Suppose 3 ∤ a and 3 ∤ b, then 3 ∤ ab. From the hypothesis, we have the following four cases: Case (i) a = 3k + 1 and b = 3h + 1. Then ab = (3k + 1)(3h + 1) = 9kh + 3(k + h) + 1 = 3(3kh + k + h) + 1. The RHS has a remainder 1 when divided by 3. So 3 ∤ ab. Case (ii) a = 3k + 2 and b = 3h + 1. Then ab = (3k + 2)(3h + 1) = 9kh + 3k + 6h + 2 = 3(3kh + k + 2h) + 2/ The RHS has a remainder 2 when divided by 3. So 3 ∤ ab. Case (iii) a = 3k + 1 and b = 3h + 2. Then ab = (3k + 1)(3h + 2) = 9kh + 6k + 3h + 2 = 3(3kh + 2k + h) + 2/ The RHS has a remainder 2 when divided by 3. So 3 ∤ ab. Case (iv) a = 3k + 2 and b = 3h + 2. Then ab = (3k + 2)(3h + 2) = 9kh + 6(k + h) + 4 = 3(3kh + 2k + 2h + 1) + 1. The RHS has a remainder 1 when divided by 3. So 3 ∤ ab. In all cases, we have 3 ∤ ab. 7. Is the following statement true? If n(n + 1) 2 is odd, then so is (n + 1)(n + 2) 2 . Page 3

H3 Math (Mathematical Proofs and Reasoning) Problem Set 1 Solution: False. Consider n = 6. Then 6(6 + 1) 2 = 21 is odd, but (6 + 1)(6 + 2) 2 = 28 is even. 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). Solution: Since j | r + s, there is an integer k ∈ Z such that kj = r + s. (⇒) Suppose a = bj + r for some b ∈ Z. Using r = jk − s, a = bj + r = bj + (jk − s) = (b + j)j − s. Let c = b + j ∈ Z. Then a = cj − s. (⇐) Suppose a = cj − s for some c ∈ Z. Using s = kj − r again, a = cj − s = cj − (kj − r) = (c − k)j + r. Let b = c − k ∈ Z. Then a = bj + r. 9. Prove that, if 3 ∤ a, then 3 | a2 + 5. Solution: Since 3 ∤ a, so its remainder is either 1 or 2 when divided by 3. Consider two cases: (i) a = 3k + 1; and (ii) a = 3k + 2. Case (i): If a = 3k + 1, then a2 + 5 = (3k + 1)2 + 5 = 9k2 + 6k + 6 = 3(3k2 + 2k + 2). Since 3k2 + 2k + 2 is an integer, we have 3 | a2 + 5. Case (ii): If a = 3k + 2, then a2 + 5 = (3k + 2)2 + 5 = 9k2 + 12k + 9 = 3(3k2 + 4k + 3). Since 3k2 + 4k + 3 is an integer, we have 3 | a2 + 5. Combining both cases, we conclude 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. Solution: Consider two cases: (i) m, nboth even; and (ii) m, nboth odd. Case (i): If m, nare even, then m = 2h and n = 2k for some integers h, k. Then m2 − n2 = (2h)2 − (2k)2 = 4(h2 − k2). Since h2 − k2 is an integer, we have 4 | m2 − n2. Case (ii): If m, nare odd, then m = 2h + 1 and n = 2k + 1 for some integers h, k. Then m2 − n2 = (2h + 1)2 − (2k + 1)2 = 4(h2 + h − k2 − k). Page 4

H3 Math (Mathematical Proofs and Reasoning) Problem Set 1 Since h2 + h − k2 − k is an integer, we have 4 | m2 − n2. Conclusion: In both cases, we have 4 | m2 − n2. Page 5

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 6