6.042/18.] Mathematics for Computer Science February 22, 2005 Srini devadas and Eric Lehman Problem set 4 Solutions Due: Monday, February 28 at 9 PM Problem 1. Prove all of the following statements except for the two that are false; for those, provide counterexamples. Assume n> 1. When proving each statement, you may assume all its predecessors (a)a≡a(modn) Solution. Every number divides zero, so n(a-a), which means a a(mod n) (b)a≡b(modn) implies b≡a(modm) Solution. The statement a= b(mod n) implies n I(a-b), which means there is an integer k such that nk =a-b. Thus, n(-k)=b-a, so n(b-a)as well. This means b≡a(modn) (c)a≡b(modm)andb≡c(modn) implies a≡c(modm) Solution. The two assumptions imply n I(a-b)and n (b-c). Thus, n divides the linear combination(a-b)+(b-c)=a-cas well. This means n (a-c) (d)a≡b(modm) implies a+c≡b+c(modm) Solution. The first statement implies n(a-b). Rewriting the right side gives nI(a+c)-(b+c), which means a+c=b+c(mod n). e)a≡b(modn) implies ac≡be(modn) Solution. The first statement implies n (a-b). Thus, n also divides c(a-b)=ac-bc Therefore, ac bc(mod n) (f)ac≡be(modn) implies a≡b(modn) provided c≠0(modm) Solution. This is false. For example,6·2≡8:2(mod4),but6≠8(mod4) (g)a≡b(modn)andc≡d(modn) imply a+c≡b+d(modm) Solution. The assumptions, together with part(e), giv a+C≡b+c(mod b+c≡b+d(modm) ow part(c)implies a+c=b+d (mod n)6.042/18.062J Mathematics for Computer Science February 22, 2005 Srini Devadas and Eric Lehman Problem Set 4 Solutions Due: Monday, February 28 at 9 PM Problem 1. Prove all of the following statements except for the two that are false; for those, provide counterexamples. Assume n > 1. When proving each statement, you may assume all its predecessors. (a) a ≡ a (mod n) Solution. Every number divides zero, so n | (a − a), which means a ≡ a (mod n). (b) a ≡ b (mod n) implies b ≡ a (mod n) Solution. The statement a ≡ b (mod n) implies n (a − b), which means there is an integer k such that nk = a −b. Thus, n(−k) = b−a | , so n | (b−a) as well. This means b ≡ a (mod n). (c) a ≡ b (mod n) and b ≡ c (mod n) implies a ≡ c (mod n) Solution. The two assumptions imply n | (a − b) and n | (b − c). Thus, n divides the linear combination (a − b) + (b − c) = a − c as well. This means n | (a − c). (d) a ≡ b (mod n) implies a + c ≡ b + c (mod n) Solution. The first statement implies n | (a − b). Rewriting the right side gives n | (a + c) − (b + c), which means a + c ≡ b + c (mod n). (e) a ≡ b (mod n) implies ac ≡ bc (mod n) Solution. The first statement implies n (a−b). Thus, n also divides c(a−b) = ac−bc. Therefore, ac ≡ bc (mod n). | (f) ac ≡ bc (mod n) implies a ≡ b (mod n) provided c �≡ 0 (mod n). Solution. This is false. For example, 6 2 · ≡ 8 · 2 (mod 4), but 6 �≡ 8 (mod 4). (g) a ≡ b (mod n) and c ≡ d (mod n) imply a + c ≡ b + d (mod n) Solution. The assumptions, together with part (e), give: a + c ≡ b + c (mod n) b + c ≡ b + d (mod n) Now part (c) implies a + c ≡ b + d (mod n)