what is the least prime p, such that mod(p, k)=1 for 18 values of k, k<= floor( sqrt(n) ) ? Answer: n=786433

Why would, among the first 100,000 primes, it be so rare for p mod k to occur just 18 times?

you are counting the number of divisors, d , of p-1 that are in the range 1 < d <= sqrt(p) . if you were to include 1 in the range, you would have half the divisors of p-1 , with the convention that if p-1 is a square, you include the divisor sqrt(p-1) . this means that your count is equivalent to floor((number_of_divisors(p-1) - 1)/ 2) . in order to get an 18 , you need p - 1 to have either 37 or 38 divisors. this means p - 1 has the form a^36 or a^18 b , where a and b are primes. since a^36 + 1 is divisible by a^4 + 1 , the first form cannot occur if p is prime. mike