Unable to start debugging on the web server - 4.5.4 ANSWERS TO EXERCISES 613 so we need
4.5.4 ANSWERS TO EXERCISES 613 so we need only verify that ci,j (pi -l)(qj -1)/4 -(p -l)(q -1)/4 (modulo 2). But ci,j (pi -l)(qj -1)/4 = (ci(pi -1)/2)(Cj(9j -1)/2) is odd iff an odd number of the pi and an odd number of the q3 are = 3 (modulo 4), and this holds iff (p -l)(q -1)/4 is odd. (b) As in exercise 22, we may assume that n = ni . . . n7 where the ni = 1 + 2kaqi are distinct primes, and Ici 5 . . . 5 k,; we let gcd(n-1, ni -1) = 2k:qi and we call z bad if it falsely makes n look prime. Let II, = nlci k, and a contradiction if ki < k. If ki = Ic, there are an odd number of lci equal to k.] Notes: The probability of a bad guess is > i only if n is a Carmichael number with k, < k; for example, n = 7.13.19 = 1729, a number made famous by Ramanujan in another context. Louis Monier has extended the above analyses to obtain the following closed formulas for the number of bad 5 in general: bn= l+q ykl- 1 d; ( > n l