For any positive integer n let w(n) denote the number of non- negative integers k such that k! = +1 or -1 (mod n). Obviously w(n) is at least 2 because 0! = 1! = +1 (mod n) for every n. Also, if p is a prime, then w(p) is at least 4, because (p-2)! = +1 and (p-1)! = -1 (mod p) by Wilson's Theorem. Not surprisingly, composite integers c such that w(c) > 2 are somewhat exceptional, there being only 44 such composites less than 10000. In contrast, primes p with large values of w(p) are not too uncommon. I call these "highly Wilsonian" primes. For example, p=23 is highly Wilsonian because 0! = 1! = 4! = 8! = 11! = 21 = +1 (mod 23) and 14! = 18! = 22! = -1 (mod 23) Another example is p=29873, for which w(p)=16, as shown below: +1 (mod 29873) -1 (mod 29873) 0! 2268! 1! 23802! 924! 26672! 1516! 28356! 3200! 28948! 6070! 29872! 7645! 22227! 27604! 29871! Of course, these are not all independent, because if k! = 1 (mod p) then clearly (p-k-1)! = +1 or -1 (mod p), depending on whether k is odd or even. I've checked all primes up to 66383, and so far the only one with w(p) > 15 is 29873 (although there are many primes with w(p)=13 and 14). (1) What is the smallest prime p such that w(p) > 16? (2) Is it true that for any positive integer m does there exist a prime p such that w(p) = m? All but one of the 45 composites mentioned above have w(c)=3. The only exception is w(121)=4. Also, all 45 of them are products of just two prime factors. (3) What is the smallest composite c > 121 with w(c)=4? (4) What is the smallest composite c with w(c) > 2 that is the product of three or more primes? In reply to question (1) above, Rob Harley (robert@cs.caltech.edu) provided the following table of the smallest primes that attain each value of w(p) from 2 to 22: w(p) p w(p) p ----- ------ ----- ------- 2 2 13 1907 3 3 14 661 4 5 15 12227 5 7 16 29873 6 17 17 96731 7 67 18 99721 8 137 19 154243 9 23 20 480209 10 61 21 ? 11 71 22 1738901 12 401 Regarding questions 3, Jud Mccranie (jud.mccranie@camcat.com) writes that he checked all composites less than 200,000 and found no more values of c > 121 with w(c) > 3. Noting that 121 is a square, he checked all squares c=x^2 for x <= 4400 and found no more cases with w(c) > 3. He did note, however, that in the range tested all of the cases of w(x^2)=3 were cases in which x was prime: N w factors 25 3 5^2 121 4 11^2 169 3 13^2 961 3 31^2 2209 3 47^2 5041 3 71^2 11449 3 107^2 316969 3 563^2 326041 3 571^2 375769 3 613^2 942841 3 971^2 So he speculates that perhaps a square can't have w > 2 unless it is the square of a prime, and perhaps w(n)=2 if n is a cube or higher power. Regarding question 4, Jud found a large number of composites n with more than two factors such that w(n) = 3. In fact, the first such number is only 5083. Here is his list: n w(n) Factors Similar forms 5083 3 13 17 23 12673 3 19 23 29 16337 3 17 31^2 1 26657 3 19 23 61 2 27931 3 17 31 53 1 29279 3 19 23 67 2 33611 3 19 29 61 3 36917 3 19 29 67 3 40687 3 23 29 61 4 44689 3 23 29 67 4 50933 3 31^2 53 77653 3 19 61 67 5 94001 3 23 61 67 5 118523 3 29 61 67 5 142069 3 17 61 137 6 144143 3 17 61 139 6 174511 3 47^2 79 He found no composites with four prime factors having w > 2.

Return to MathPages Main Menu