Formal MethodsKey to Homework Assignment 2, Part 3February 7, 2007• Prove that the integer n is even iff −n is even.Since this is an e quivalence, we need to prove two implications: n even implies −neven, and −n even implies n even.1. Proof that n even implies −n even. If n is even, there is an integer k such thatn = 2k. So −n = −2k = 2(−k), and if we define l = −k, l is an integer such that−n = 2l. So −n is even.2. Proof that −n even implies n even. If −n is even, there is an integer k such that−n = 2k. So n = −(−n) = −2k = 2(−k), and l = −k is an integer such thatn = 2k. So n is even.• Prove that if n is an integer, then there exists an integer k such that n = 2k + 1 iffthere exists an integer m such that n = 2m − 1.Once again, since this is an equivalence we need to prove two implications: ∃k suchthat n = 2k + 1 implies ∃m such that n = 2m − 1, and ∃m such that n = 2m − 1implies ∃k such that n = 2k + 1.1. Proof that ∃k such that n = 2k + 1 implies ∃m such that n = 2m − 1. If there isan integer k such that n = 2k + 1, thenn = 2k + (2 − 2) + 1 = (2k + 2) − 1 = 2(k + 1) − 1.So if we define m = k + 1, we see that n = 2m − 1.2. Proof that ∃m such that n = 2m − 1 implies ∃k such that n = 2k + 1. If there isan integer m such that n = 2m − 1, thenn = 2m + (−2 + 2) − 1 = (2m − 2) + 1 = 2(m − 1) + 1.So if we define k = m − 1, we see that n = 2k + 1.62. Let A, B, C , M, and N be integers. Prove that if A divides each of B and C, then Adivides NB + MC.1Proof. Suppose that A|B and A|C. Then there exist integers k and l such that Ak = Band Al = C. (We need to find an integer p such that Ap = NB + MC.) We haveNB + MC = NAk + MAl = A(Nk + Ml).So if we define p = Nk + M l, we see that Ap = NB + MC and A|(NB + MC).63. Let A be an even integer and B be an odd integer. Prove that A + B is odd and ABis even.Proof. Since A is even and B is odd, there exist integers k and l such that A = 2kand B = 2l + 1. SoA + B = 2k + (2l + 1) = 2(k + l) + 1,and if we define p = k + l, we see that p is an integer such that A + B = 2p + 1. SoA + B is odd.We also haveAB = (2k)(2l + 1) = 2[k(2l + 1)],and if we define q = k(2l + 1), q is an integer such that AB = 2q and AB is even.67. Let A and B be integers. Prove that if AB is odd, then A + B is even.To prove this, we first prove a couple of familiar results.– AB is odd iff both A and B are odd.We need to see that AB odd implies both A and B are odd, and both A and Bodd implies AB odd.First we give a direct proof that A and B odd implies AB odd. Since A and Bare odd, there exist integers k and l such that A = 2k + 1 and B = 2l + 1. SoAB = (2k + 1)(2l + 1) = 4kl + 2k + 2l + 1 = 2(2kl + k + l) + 1.So if we define p = 2kl + k + l, then AB = 2p + 1 and AB is odd.To prove the converse, AB odd implies that both A and B are odd, we provethe contrapositive: if at least one of A and B is even, then AB is even. (Thisassumes the result we proved in class that every integer is odd or even, but notboth.) Suppose that A is even. Then there exists an integer k such that A = 2k.So AB = (2k)B = 2(kB), and if we define p = kB, then p is an integer such thatAB = 2p, and AB is even. The proof in case B is even is virtually identical, andwe omit it.– A + B is even iff both A and B are even or both A and B are odd.Another way to say “both A and B are even or both A and B are odd” is “A andB have the same parity.” So the result can be restated as A + B is even iff A andB have the same parity.Since this is an equivalence, we need to prove A + B even implies A and B havethe same parity, and A and B have the same parity implies A + B is even.2First we give a direct proof of A and B have the same parity implies A + B iseven. We consider the two cases: both A and B are even and both A and B areodd. If both A and B are even, then there exist integers k and l such that A = 2kand B = 2l. So A + B = 2k + 2l = 2(k + l), and A + B is even in this case. Ifboth A and B are odd, there exist integers m and n such that A = 2m + 1 andB = 2n + 1. So A + B = (2m + 1) + (2n + 1) = 2(m + n + 1), and A + B is alsoeven in this case.To prove the converse, we prove the contrapositive: if A and B have differentparities, then A + B is odd. So suppose A is even and B is odd. Then there existintegers k and m such that A = 2k and B = 2m + 1. So A + B = 2k + 2m + 1 =2(k + m) + 1 and A + B is odd. A completely analogous proof shows that A + Bis odd when A is odd and B is even.Proof of Result. If we assume that AB is odd, then by the first result, both A andB are odd. So by the second result A + B is even.70. Let n be an integer such that n2is even. Prove that n2is divisible by 4.Proof. We proved in class that n is even iff n2is even. So if we assume that n2is even,then n is even. So there exists an integer k such that n = 2k. Thus n2= (2k)2= 4k2,and if we define m = k2, m is an integer such that n2= 4m. So n2is divisible by …