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 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 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