Problem set 4 h)a≡b(modm)andc≡d(modn) imply ac≡bd(modn) Solution. The assumptions, together with part(e), give aC≡bc(modm) be≡bd(modn) Now part(c)implies ac bc(mod n) i)a≡b(modm)imp b(modn) for all k≥0 Solution. We use induction. Suppose that a= b(mod n). Let P(k)be the proposi Base case. P(O)is true, since a=b=l and 1= 1(mod n)by part(a) Inductive step.Fork≥0, we assume p(k) to prove F(k+1).Thus, assume a≡砂 (mod n). Combining this assmption and the fact that a= b(mod n)using part (g), e get a+1≡b+1(modn) By induction, P(k)holds for all k>0 ()a≡b(modn) implies ko≡kb(modn) for all k≥0. Solution. This is false. For example, 0=3(mod 3), but 20#23(mod 3) k)( a rem n)≡a(modn) Solution. By definition of rem, a rem n=a- qn for some integer q. So we can reason as follows: a rein = nod n mo from( d)and qn=0(mod n) Problem 2. Prove that there exists an integer k-l such that k·k-1=1(modn) provided gcd(k, n)=1. Assume n>1 Solution. If gcd(k, m)= 1, then there exist integers r and y such that kr yn=1 Therefore, yn=1-kar, which means n (1-k )and so k=1(mod n). Let k- be r Problem 3. Reviewing the analysis of Sa may help you solve the following problems You may assume results proved in recitation (a)Let n be a nonnegative integer. Prove that n and n have the same last digit. For example =3077056399 Solution. The correctness of RSa relies on the following fact: if p and q are distinct primes, then for all m and k Setting k=l, p=5, and q=2 proves the claim.2 Problem Set 4 (h) a ≡ b (mod n) and c ≡ d (mod n) imply ac ≡ bd (mod n) Solution. The assumptions, together with part (e), give: ac ≡ bc (mod n) bc ≡ bd (mod n) Now part (c) implies ac ≡ bc (mod n). (i) a ≡ b (mod n) implies ak ≡ bk (mod n) for all k ≥ 0. Solution. We use induction. Suppose that a ≡ b (mod n). Let P(k) be the proposi￾k tion that a ≡ bk . 0 Base case. P(0) is true, since a = b0 = 1 and 1 ≡ 1 (mod n) by part (a). k Inductive step. For k ≥ 0, we assume P(k) to prove P(k + 1). Thus, assume a ≡ bk (mod n). Combining this assmption and the fact that a ≡ b (mod n) using part (g), k+1 ≡ b we k+1 get a (mod n). By induction, P(k) holds for all k ≥ 0. (j) a ≡ b (mod n) implies ka ≡ kb (mod n) for all k ≥ 0. Solution. This is false. For example, 0 ≡ 3 (mod 3), but 20 �≡ 23 (mod 3). (k) (a rem n) ≡ a (mod n) Solution. By definition of rem , a rem n = a − qn for some integer q. So we can reason as follows: (a rem n) ≡ a − qn (mod n) ≡ a (mod n) from (d) and qn ≡ 0 (mod n) Problem 2. Prove that there exists an integer k−1 such that k k−1 · ≡ 1 (mod n) provided gcd(k, n) = 1. Assume n > 1. Solution. If gcd(k, n) = 1, then there exist integers x and y such that kx + yn = 1. Therefore, yn = 1 − kx, which means n (1 − kx) and so kx ≡ 1 (mod n). Let k−1 | be x. Problem 3. Reviewing the analysis of RSA may help you solve the following problems. You may assume results proved in recitation. (a) Let n be a nonnegative integer. Prove that n and n5 have the same last digit. For example: 25 = 32 795 = 3077056399 Solution. The correctness of RSA relies on the following fact: if p and q are distinct primes, then m 1+k(p−1)(q−1) ≡ m (mod pq) for all m and k. Setting k = 1, p = 5, and q = 2 proves the claim