## Exercises #### Section 10.1 1. Find the positive divisors of the following integers. 1. 72 2. 31 3. 123 2. Prove that if *h|m* and *m|n*, and *h|n.* 3. show that two integers divide each other if and only if they are equal. 4. Let *p* and *q* be two prime numbers. If *p* = *q* + 2, then *p* and *q* are called "twin prime numbers." Find two pairs of twin prime numbers. 5. Prove that gcd (*n,m*) = gcd (*m,n*). 6. Prove that if *m* and *n* are both even, then gcd (*m,n*) = 2 gcd (*m*/2, *n*/2). 7. Prove that if *n* ≥ *m* > 0, then gcd (*m,n*) = gcd (*m,n -m*). 8. Prove that if *p* is a prime number and 0 < *h* < *p*, then gcd (*p,h*) = 1. 9. Use [Corollary 10.2](LiB0081.html#1018) to show that the prime factorization of an integer, as discussed in [Theorem 10.5](LiB0081.html#1019), is unique. 10. Write each of the following integers as a product of prime numbers. 1. 123 2. 375 3. 927 11. Prove [Theorem 10.6](LiB0081.html#1022). 12. Prove [Theorem 10.7](LiB0081.html#1027). 13. Prove that of positive integers *m* and *n*, gcd (*m,n*) iff *m* = *n*. #### Section 10.2 1. Illustrate the flow of [Algorithm 10.1](LiB0082.html#1033) when the top-level call is gcd (68, 40). 2. Write an iterative version of [Algorithm 10.1](LiB0082.html#1033) Your algorithm should only use a constant amount of memory \[i.e., the space complexity function is in θ(1)\]. 3. Write an algorithm that uses [Algorithm 10.1](LiB0082.html#1033) to express a rational number in its lowest terms. You may assume that this rational number is given in the form of a fraction *m/n* where *m* and *n* are integers. 4. Illustrate the flow of [Algorithm 10.2](LiB0082.html#1043) when the top-level call is *Euclid*(64, 40, *gcd,i,j*). 5. Write an algorithm that uses subtraction to compute the greatest common divisor. (See Exercise 7.) Analyze your algorithm. #### Section 10.3 1. Show that (*S*,\*) of Example 10.21 is a group. 2. Prove [Theorem 10.12](LiB0083.html#1060). 3. The following was left as an exercise in the proof of [Theorem 10.13](LiB0083.html#1062). Show that there exists an integer *c* such that *h*1 = *cn*2*n*3…*nj*. 4. Prove [Theorem 10.14](LiB0083.html#1066). 5. Prove that if *s* ∊\[*m*\]n and *t* ∊\[*k*\]*n* then *s* ×*t* ∊\[*m* ×*k*\]*n*. 6. Show that if *G*=(*S*,\*) is a finite group and *a* ∊ *S*, then there exists integers *k,m* ≥ 1 such that ak=akam. 7. Show that if *S*= {\[0\]}12,\[3\]12,\[6\]12,\[9\]12}, then (*S*,+) is a subgroup of (**Z**12, +). 8. Use [Theorem 10.19](LiB0083.html#1089) to prove [Corollary 10.3](LiB0083.html#1091). 9. Consider the group (**Z**\*9,×). Show that 〈\[2\]9〉 = **Z**\*9. #### Section 10.4 1. Solve the following modular equations. 1. \[8\]10*x*=\[4\]10 2. \[4\]17 x=\[5\]17 2. Implement [Algorithm 10.3](LiB0084.html#1128) and run it on various problem instances. 3. Find all solutions to the equations \[1\]7*x* = \[3\]7 and \[12\]9*x* = \[6\]9. #### Section 10.5 1. Compute (\[3\]73)12 by raising 3 to the 12th power. 2. Compute (\[7\]73)15 by raising 7 to the 15th power. 3. Use [Algorithm 10.4](LiB0085.html#1132) to compute (\[3\]73)12. 4. Use [Algorithm 10.4](LiB0085.html#1132) to compute (\[7\]73)15. 5. Implement [Algorithm 10.4](LiB0085.html#1132), and run it on various problem instances. #### Section 10.6 1. Find the number of prime numbers that are less than or equal to 100. 2. If an integer between 1 and 10,000 is randomly chosen according to the uniform distribution, approximately what is the probability of it being prime? 3. Suppose we randomly choose 100 numbers between 1 and 10,000 according to the uniform distribution. Approximately, what is the probability of all of them not being prime? 4. Show that if *n* is prime and 1 < *k* ≤ *n* -1, then *B*(*n,k*) ≡ 0 mod *n*, where B(m,k) denotes the binomial coefficient. 5. Show that if *q* is a factor of *n* and *k* is the order of *q* in *n*, then *qk*|*B* (*n,q*), where *B*(*n,q*) denotes the binomial coefficient. 6. Are 9*x*3 + 2*x* and *x*2 - 4 congruent modulo 2? 7. Show that (x-9)4 is not congruent to (x4-9) modulo 4. 8. Show that (x-5)3 is congruent to (x3-5) modulo 3. 9. Prove [Theorem 10.29](LiB0086.html#1164). 10. Implement [Algorithm 10.5](LiB0086.html#1167) and run it on different problem instances. 11. Use [Lemma 10.3](LiB0086.html#1171) to prove [Lemma 10.4](LiB0086.html#1173). 12. The following was left as an exercise in the proof of [Lemma 10.6](LiB0086.html#1176). Show *ordr*(*n*)|lcm*ordr*(*p*1), *ordr*(*p*2), … *ordr*(*pk*)). 13. Use Inequality 10.22 to obtain the inequality that follows it. #### Section 10.7 1. What is the difference between a public key and a secret key? 2. Consider an RSA cryptosystem using *p* = 7, *q* = 11 and *g* = 13. 1. Compute *n*. 2. Compute φ 3. Find *h*. 3. Consider an RSA cryptosystem using *p* = 23, *q* = 41 and *g* = 3. Encipher the message \[847\]943. 4. Use the RSA cryptosystem of Exercise 51 to decrypt the encrypted message found in that exercise. 5. In an RSA cryptosystem, show that if φ(n) can be discovered, then the cryptosystem may be compromised. #### Additional Exercises 1. Prove that there are infinitely many prime numbers. 2. Show that the gcd operator is associative. That is, for all integers *m,n,* and *h,* we have gcd (*m, gcd* (*n,h*)) = gcd (gcd (*m,n),h*). 3. Prove that if *m* is odd and *n* is even, then gcd (*m, n*) = gcd (*m,n*/2). 4. Prove that if *m* and *n* are both odd, then gcd (*m, n*) = gcd (*m - n*)/2, *n*). 5. Find the necessary condition to have equation *mx* ≡ *my* mod *n* imply *x* ≡ *y* mod *n*. 6. Assuming that *p* is a prime number, find the solutions of the equation *x*2 = \[1\]*p*. 7. In an RSA Cryptosystem, let *p* and *q* be the large primes, let *n* = *pq*, and let *pub* be the public key. Show that *pub*(*a*)*pub*(*b*) is congruent to *pub(ab)* modulo *n*.