Web hosting contract - 4.5.4 ANSWERS TO EXERCISES 609 5. zmod3 =
4.5.4 ANSWERS TO EXERCISES 609 5. zmod3 = 0; smod5 = 0, 1, 4; smod7 = 0, 1, 6; zmod8 = 1, 3, 5, 7; 5 > 103. The first try is z = 105; and (105) -10541 = 484 = 222. This would also have been found by Algorithm C in a relatively short time. Thus 10541 = 83. 127. 6. Let us count the number of solutions (z, y) of the congruence N E (z -y)(z + y) (modulo p), where 0 < 2, y < p. Since N $ 0 and p is prime, z + y $ 0. For each u $ 0 there is a unique u (modulo p) such that N E UV. The congruences 5 -y E U, z + y E Y now uniquely determine x mod p and y mod p, since p is odd. Thus the stated congruence has exactly p -1 solutions (2;~). If (2, y) is a solution, so is (z, p -y) if y # 0, since (p -y) E y2; and if (5, yi) and (z, ~2) are solutions with yl # y2, we have y: E yi; hence yi = p -ys. Thus the number of different 2 values among the solutions (x, y) is (p -1)/2 if N E x2 has no solutions, or (p + 1)/2 if N EE 2 has solutions. 7. One procedure is to keep two indices for each modulus, one for the current word position and one for the current bit position; loading two words of the table and doing an indexed shift command will bring the table entries into proper alignment. (Many computers have special facilities for such bit manipulation.) 8. (We may assume that iV = 2M is even.) The following algorithm uses an auxiliary table X[l], X[2], , X[M], where X[k] represents the primality of 2k + 1. Sl. Set X[lc] t 1 for 1 5 k < M. Also set j + 1, p t 1, p t 3, q + 4. (During this algorithm p = 2j + 1, q = 2j $ 2j2; the integer variables j, k, p, q may readily be manipulated in index registers.) S2. If X[j] = 0, go to S4. Otherwise output p, which is prime, and set k + q. S3. If k 5 M, then set X[k] + 0, k + k + p, and repeat this step. S4. Setjtj+l,p+p+2,qcq+2p-2.Ifj< M,returntoS2. l A major part of this calculation could be made noticeably faster if q (instead of j) were tested against M in step S4, and if a new loop were appended that outputs 2j + 1 for all remaining X[j] that equal 1, suppressing the manipulation of p and q. Improvements in the efficiency of sieve methods for generating primes are discussed in exercise 5.2.3-15 and in Section 7.1. 9. If p2 is a divisor of n for some prime p, then p is a divisor of x(n), but not of n-1. If n = pips, where pl < p2 are primes, then ps -1 is a divisor of x(n) and therefore plp2 -1 = 0 (modulo ps -1). Since ps E 1, this means pi -1 is a multiple of p2 -1, contradicting the assumption pl < ps. [Values of n for which x(n) properly divides n -1 are called Carmichael numbers. For example, here are some small Carmichael numbers with up to six prime factors: 3.11.17, 5.13.17, 7.11.13.41, 5.7.17.19.73, 5 7.17 73 89.107.1 10. Let k, be the order of zP modulo n, and let X be the least common multiple of all the k, s. Then X is a divisor of n -1 but not of any (n -1)/p, so X = n -1. Since z;(n) modn = 1, p(n) is a multiple of k, for all p, so p(n) > X. But p(n) < n -1 when n is not prime. (Another way to carry out the proof is to construct an element z of order n -1 from the zP s, by the method of exercise 3.2.1.2-15.)