Shared web hosting - 614 ANSWERS TO EXERCISES 4.5.4 to +(z is
614 ANSWERS TO EXERCISES 4.5.4 to +(z is prime) + constant + szm dt/(t -1)t In t. The constant is li 2 -In 2 = y + InIn + xn,z(ln2) /nn! = 0.35201 65995 57547 47542 73567 67736 43656 84471+. - 26. If N is not prime, it has a prime factor 4 2 fi. By hypothesis, every prime divisor p of f has an integer xp such that the order of xp modulo q is a divisor of N -1 but not of (N -1)/p. Therefore if pk divides f, the order of xp modulo q is a multiple of pk. Exercise 3.2.1.2-15 now tells us that there is an element x of order f modulo q. But this is impossible, since it implies that q2 2 (f + 1)2 2 (f + 1) r 2: N, and equality cannot hold. [Proc. Camb. Phil. Sot. 18 (1914), 29-30.1 27. If k is not divisible by 3 and if k 5 2n + 1, the number k.2 + 1 is prime iff 3 2 - k -= -1 (modulo k.2 + 1). For if this condition holds, k.2n + 1 is prime by exercise 26; and if k.2 + 1 is prime, the number 3 is a quadratic nonresidue mod k.2 + 1 by the law of quadratic reciprocity, since k.2 + 1 mod 12 = 5. [This test was stated without proof by Proth in Comptes Rendus 87 (Paris, 1878), 926.1 To implement Proth s test with the necessary efficiency, we need to be able to compute x2 mod (k.2 + 1) with about the same speed as we can compute the quantity x2 mod(2 -1). Let x 2 = A.2 + B and let A = qk + r where 0 5 r < k; we can determine q and r rapidly, when k is a single-precision number. Then x2 E B -q + r.2% (modulo k.2 + l), so the remainder is easily obtained. [To test numbers of the form 3.2 + 1 for primality, the job is only slightly more difficult; we first try random single-precision numbers until finding one that is a quadratic nonresidue mod 3.2 + 1 by the law of quadratic reciprocity, then use this number in place of 3 in the above test. If nmod4 # 0, the number 5 can be used. It turns out that 3.2n + 1 is prime when n = 1, 2, 5, 6, 8, 12, 18, 30, 36, 41, 66, 189, 201, 209, 276, 353, 408, 438, 534, 2208, 2816, 3168, 3189, 3912; and 5.2n + 1 is prime when n = 1, 3, 7, 13, 15, 25, 39, 55, 75, 85, 127, 1947. See R. M. Robinson, Proc. Amer. Math. Sot. 9 (1958), 673-681; the additional numbers listed here were found by M. F. Plass.] 28. f(~, p2d) = 2/(~ + 1) + f(~, WP, since l/(p f 1) is the probability that A is a multiple of p. f(p, pd) = l/(p f 1) when dmodp # 0. f(2,4k + 3) = 3 since A2 -(4k + 3)B2 cannot be a multiple of 4; f(2,8k f 5) = $j since A2 -(8k + 5)B2 cannot be a multiple of 8; f(2,8k + 1) = 4 $ 4 $ i $ Q $ & + . . . = 3. f(p, d) = (2p/(p -l), 0) if d(p-1)/2 modp = (1, p -l), respectively, for odd p. 29. The number of solutions to the equation x1 $. . . + xm 5 r in nonnegative integers ziis(m$7) _> mr / r!, and each of these corresponds to a unique integer p; . . pkm 2 n. [For sharper estimates, in the special case that p, is the jth prime for all j, see N. G. de Bruijn, Indag. Math. 28 (1966), 240-247; H. Halberstam, Proc. London Math. Sot. (3) 21 (1970), 102-107.1 30. If p; . . .pz = xf (modulo qt), we can find yi such that pi . . .p$ = (j-yi) (modulo q$), hence by the Chinese remainder theorem we obtain 2d values of X such that X2 = pql. . . pz (modulo N). Such (el, . . . , e,) correspond to at most (r;2) pairs (e: ,…, el,;ey,.. , ek) having the hinted properties. Now for each of the 2d binary numbers a = (al . . . ad)2, let n, be the number of exponents (e:, . . . , eh) such that L.p l ) (qt-1)/2 f (-l) z (modulo qi); we have proved that the required number bpflintege;s X is 2 2d(C, nz)/(,;,). S mce c, na is the number of ways to choose at most r/2 objects from a set of m objects with repetitions permitted, namely ( z; 2), we have c, n , 2 ( m;t/; 2)2/2d 2 m /(2d(r/2)!). [Cf. J. Number Theory, to appear.]