Highly Wilsonian Primes

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