4. Problems 2 and 3 on this homework assignment indicate how (surprisingly?) useful the Division Algorithm can be, with particular emphasis on remainders. To practice grappling with new definitions (something math and CS courses will throw at you all the time), let's introduce a new definition here, based on the "importance of remainders." Def. Let n E Z. Two integer are said to be congruent modulo n provided that they have the same remainder when divided by n. For x, y E Z, we denote this as r = y mod n. (a) (3 points) Explain (in your own words or in an "official proof ) why two integers being congruent mod 2 means they have the same parity. (b) (3 points) Which integers are congruent to 1 mod 5? Answer this question by circling one or more of the given sets below, the one(s) that correctly describes (or lists) all such integers. i. {.. ., -10, -5, 0, 5, 10, 15, . . . } ii. {5k + 1 : kez}. iii. { . ..,-7, -4, -1, 2, 5, 8, . .. }. iv. {. ..,-11, -6, -1, 4, 9, 14, . . . }. v. {5k - 1 : ke Z). (c) (4 points) Portions of a proof (for a proposition related to this concept of congruence mod n) are presented below. Fill in the missing blanks. (1 points each). Proposition. If x = y mod n then n|(x - y). proof. Suppose n, , y E Z and suppose that This means r and y have the same remainder when divided by n. According to the then, 391, 92 and r E Z, * =qin+r (1) y = q2 n + r (2 ) By subtracting equations (1) and (2) we see that x- y = (91 - q2)n. Since Z is closed under it follows that q1 - 92 E Z. Finally, this last equation shows that n divides