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)
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 proposik 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
Problem Set 4 (b) Suppose that p1,..., Pk are distinct primes. Prove that 1+(P1-1)(P2-1)…(Pk-1) (modp1p2…pk) for all m and all k> 1 Solution. If m is a multiple of a (P1-1)(P2-1)…(Pk-1) (mod pi) holds, because both sides are congruent to 0. If m is not a multiple of pi, then con gruence()still holds because: m+(-1(-)0k-1)≡m·(m-1)p-m-p)-0/0-1)(modp) 小m,1m-1)2-m-1/(1-1)(modp2) (mod pi The second step uses Fermat's Theorem Now the congruence()means that P|m1+(p1-1)p2-1)-(pk-1)-m Thus, P; appears in the prime factorization of right side. Since this argument is valid for every prime p, where 12, then p-l and l are distinct terms in the product 1 ese are the
Problem Set 4 3 (b) Suppose that p1, . . . , pk are distinct primes. Prove that m1+(p1−1)(p2−1)···(pk−1) ≡ m (mod p1p2 · · · pk) for all m and all k ≥ 1. Solution. If m is a multiple of a prime pj , then m1+(p1−1)(p2−1)···(pk−1) ≡ m (mod pj ) (*) holds, because both sides are congruent to 0. If m is not a multiple of pj , then congruence (*) still holds because: m1+(p1−1)(p2−1)···(pk−1) ≡ m · (mpj−1 ) (p1−1)(p2−1)···(pk−1)/(pj−1) (mod pj ) ≡ m · 1 (mod pj ) (p1−1)(p2−1)···(pk−1)/(pj−1) ≡ m (mod pj ) The second step uses Fermat’s Theorem. Now the congruence (*) means that: m1+(p1−1)(p2−1)···(pk−1) pj | − m Thus, pj appears in the prime factorization of right side. Since this argument is valid for every prime pj where 1 ≤ j ≤ k, all of the primes p1, . . . , pk appear in the prime factorization of: 1+(p1−1)(p2−1)···(pk−1) m − m Therefore: p1p2 m1+(p1−1)(p2−1)···(pk−1) · · · pk | − m Rewriting this as a congruence gives: m1+(p1−1)(p2−1)···(pk−1) ≡ m (mod p1p2 · · · pk) Problem 4. Suppose that p is a prime. (a) An integer k is selfinverseif k·k ≡ 1 (mod p). Find all integers that are selfinverse mod p. Solution. The congruence holds if and only if p k2 − 1 which is equivalent to p (k + 1)(k − 1). this holds if and only if either p | | | | k + 1 or p k − 1. Thus, k ≡ ±1 (mod p). (b) Wilson’s Theorem says that (p−1)! ≡ −1 (mod p). The English mathematician Edward Waring said that this statement would probably be extremely difficult to prove because no one had even devised an adequate notation for dealing with primes. (Gauss proved it while standing.) Your turn! Stand up, if you like, and try cancelling terms of (p − 1)! in pairs. Solution. If p = 2, then the theorem holds, because 1! ≡ −1 (mod 2). If p > 2, then p − 1 and 1 are distinct terms in the product 1 2 · · · · ·(p − 1), and these are the
Problem set 4 only self-inverses. Consequently, we can pair each of the remaining terms with its multiplicative inverse. Since the product of a number and its inverse is congruent to 1, all of these remaining terms cancel. Therefore, we have (mod p (mod P)
4 Problem Set 4 only selfinverses. Consequently, we can pair each of the remaining terms with its multiplicative inverse. Since the product of a number and its inverse is congruent to 1, all of these remaining terms cancel. Therefore, we have: (p − 1)! ( ≡ 1 · p − 1) (mod p) ≡ −1 (mod p)