Formal MethodsKey to Homework Assignment 2, Part 2February 5, 2007pp. 30-31: 56, 57, 58 (the definition of divides is on p. 22), 59ab, 60 (you can use the factthat if 2 divides mn, then 2 divides m or 2 divides n).56. Prove that any multiple of an even integer is even.This can be written using quantifiers as∀ integers n [(n a multiple of an even integer) → (n even)].Proof. Suppose that n is an integer and n is a multiple of an even integer. (We needto find an integer p such that n = 2p.) Since n is a multiple of an even integer, there isan even integer k and an integer l such that n = kl. Since k is even, there is an integerm such that k = 2m. Son = kl = (2m)l = 2(ml),and p = ml is an integer such that n = 2p.57. Prove that the sum of two even integers is even.This can be written using quantifiers as∀ integers m, n [(m, n even) → (m + n even)].Proof. Suppose that m and n are even integers. Then there exist integers k and lsuch that m = 2k and n = 2l. We want to see that m + n is even. That is, we want tofind an integer p such that m + n = 2p. Since m = 2k and n = 2l , we havem + n = 2k + 2l = 2(k + l).So if p = k + l, we see that p is an integer such that m + n = 2p, and m + n is even.58. Let A, B, and C be integers. Prove that if A|B and B|C, then A|C.Proof. Suppose that A, B, and C are integers such that A|B and B|C. Then thereexist integers k and l such that Ak = B, and Bl = C. We want to see that A|C. So wewant to find an integer m such that Am = C. But since Ak = B, we haveC = Bl = (Ak)l = A(kl).So if we define m = kl, m is an integer such that Am = C, and A|C.159. Let A and B be integers and let D be a positive integer.(a) Prove the following proposition: If D divides A and D divides B, then D dividesboth A + B and A − B.Proof. Since D|A and D|B, there exist integers k and l such that Dk = A andDl = B. ThusA + B = Dk + Dl = D(k + l),andA − B = Dk − Dl = D(k − l).Since k + l and k − l are integers D divides A + B and D divides A − B.(b) Is the converse of the proposition given in (a) true? If so, prove it; if not, give acounterexample.The converse says that if D divides A + B and D divides A − B, then D dividesA and D divides B. This is false. For example, if D = 2, and A = B = 1, then Ddivides A + B = 2, and D divides A − B = 0, but D do esn’t divide either A or B.60. Prove that if D is an odd integer that divides both the sum and difference of twointegers A and B, then D divides both A and B.Proof. Suppose that D divides A + B and D divides A − B. Then there exist integersk and l such that Dk = A + B and Dl = A − B. SoD(k + l) = Dk + Dl = A + B + A − B = 2A.SimilarlyD(k − l) = Dk − Dl = A + B − A + B = 2B.So 2 divides D(k + l) and 2 divides D(k − l). But according to the result given in theassignment, if 2 divides mn then 2 divides m or 2 divides n. Since D is odd, 2 doesn’tdivide D. So 2|(k + l) and 2|(k − l). So there exist integers p and r such that 2p = k + land 2r = k − l. This gives us thatD(k + l) = 2pD = 2A, and D(k − l) = 2rD = 2B.Dividing the equations 2pD = 2A and 2rD = 2B by 2 gives us that pD = A, andrD = B. Since p and r are integers, D|A and