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