Php web hosting - 394 ARITHMETIC 4.5.4 Since n is prime, the
394 ARITHMETIC 4.5.4 Since n is prime, the binomial coefficient is divisible by n except when k = 0 and Ic = (n + 1)/2; hence 2(n-1)/2 V2,-I s 1 + 3(n+1)/2 (modulo n). Here 2 z (2(9f1)/2)2, so 2(n-1)/2 E (2(qf1)/2)(n-1) E 1 by Fermat s theorem. Finally, by a simple case of the law of quadratic reciprocity (cf. exercise 23), 3(n-1)/2 E -1, since nmod 3 = 1 and nmod4 = 3. This means V2s-~ e -2, so v&?-z F 0. # The world s largest explicitly known prime numbers have always been Mer- senne primes, at least from 1772 until 1980 when this book was written. But the situation will probably change soon, since Mersenne primes are getting harder to find, and since exercise 27 presents an efficient test for primes of other forms. EXERCISES 1. [IO] If the sequence do, dl, dz, . . . of trial divisors in Algorithm A contains a number that is not prime, why will it never appear in the output? 2. [~5] If it is known that the input N to Algorithm A is equal to 3 or more, could step A2 be eliminated? 3. [ML%] Show that there is a number P with the following property: If 1000 2 n 2 1000000, then n is prime if and only if gcd(n, P) = 1. 4. [MZ 9] In the notation of exercise 3.1-7 and Section 1.2.11.3, prove that the average value of the least n such that X, = X lcn)–l lies between 1.5&(m) -0.5 and 1.625 Q(m) -0.5. 5. [,%I Use Fermat s method (Algorithm D) to find the factors of 10541 by hand, when the moduli are 3, 5, 7, and 8. 6. [M24] If p is an odd prime and if N is not a multiple of p, prove that the number of integers 2 such that 0 < z < p and x2 -N E y2 (modulo p) has a solution y is equal to (p f 1)/2. 7. [%I Discuss the problems of programming the sieve of Algorithm D on a binary computer when the table entries for modulus rni do not exactly fill an integral number of memory words. b 8. [%?I (The sieve of Eratosthenes, 3rd century B.C.) The following procedure evidently discovers all odd prime numbers less than a given integer N, since it removes all the nonprime numbers: Start with all the odd numbers less than N; then successively strike out the multiples p:, pk(pk + 2), pk(pk + 4), . . . , of the kth prime pk, for /c = 2, 3, 4, . . . , until reaching a prime pk with p: > iv. Show how to adapt the procedure just described into an algorithm that is directly suited to efficient computer calculation, using no multiplication.