On the converse of Wolstenholme's Theorem

Abstract

The problem of distinguishing prime numbers from composite numbers (. . .) is known to be one of the most important and useful in arithmetic. (. . .) The dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated. Wilson’s Theorem states that if p is prime then (p− 1)! ≡ −1 (mod p). It is easy to see that the converse of Wilson’s Theorem also holds. Thus Wilson’s Theorem can be used to identify the primes. Another congruence identifying the primes is (p+ 1)(2p+ 1)(3p+ 1) . . . ((p− 1)p+ 1) ≡ 0 (mod (p− 1)!). (For a proof see [21].) It is not difficult to show that (2p−1 p−1 ) ≡ 1 (mod p) for all primes p. In 1819 Babbage [5, p. 271] observed that the stronger congruence (2p−1 p−1 ) ≡ 1 (mod p2) holds for all primes p ≥ 3, and Wolstenholme [5, p. 271], in 1862, proved that (2p−1 p−1 ) ≡ 1 (mod p3) for all primes p ≥ 5. The congruence (2n−1 n−1 ) ≡ 1 (mod n3) has no composite solutions n < 109. J. P. Jones ([9, problem B31, p. 47], [23, p. 21] and [12]) has conjectured that there are no composite solutions. Unlike that of Wilson’s Theorem the converse of Wolstenholme’s Theorem is a very difficult problem. A set S of positive integers is a Diophantine set if there exists a polynomial P (n, x1, . . . , xm) with integer coefficients such that n ∈ S if and only if there exist nonnegative integers x1, . . . , xm for which P (n, x1, . . . , xm) = 0. If we define Q(n, x1, . . . , xm) = n(1 − P (n, x1, . . . , xm)), then the set S is identical to the positive range of Q as n, x1, . . . , xm range over the nonnegative integers. One of the most important results obtained in the investigation of Hilbert’s tenth problem (which asks for an algorithm to decide whether a