Contents

Gauss (Disquisitiones Arithmeticae, 1801, art. 329) wrote:

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.

In 1773 Lagrange observed that Wilson's Theorem could be used to identify primes by writing it in the form

An integer is prime if and only ifndivides .

In connection with the solution of Hilbert's Tenth Problem, Matijasevic
(1971) constructed an integer polynomial **f** (in many variables)
such that the set of positive values of **f** is exactly the set of
prime numbers (see [11] for an elegant construction).
The construction is based on Lagrange's reformulation of Wilson's Theorem.
Professor J.P. Jones has asked whether a similar criteria to identify
primes can be obtained from Wolstenholme's congruence: that is,
whether it is true that (1.4) holds if and only if **p** is a prime .
(R. McIntosh has shown that the
congruence can hold for composite and even
for ; thus the `3' is certainly necessary.)
One might also ask the same question based on the generalization (1.5)
of Wolstenholme's Theorem, or on (1.6).

As far back as 1819, Babbage gave an easily proved characterization of the primes, based on a number of simultaneous congruences:

An integer is prime if and only if for all

(Notice that the range for **m** may be shortened to ).

In 1972, Mann and Shanks [17] came up with another characterization involving a number of simultaneous congruences:

An integer is prime if and only ifmdivides for all

(Notice that the range for **m** may be shortened to ). To prove this note first that if **n** is prime then
, which is
clearly divisible by **m**, as .
On the other hand, if even **n** is composite
take so that **m** does not divide , and
if odd **n** is composite and divisible by prime **p** take .
If is the highest
power of **p** that divides **m** (note that ) then it is easy to
show that is the highest power of **p** that divides ,
by Kummer's Theorem.

In 1915 Fleck gave an imaginative generalization of Wilson's Theorem, that can be used to characterize primes after a certain amount of trial division:

For any integers andn, free of prime factors , we have thatnis prime if and only if

(Actually Fleck did not include the condition that **n** is free
of prime factors but some such condition is essential as
(4.1) holds for the example .)
To see this, note first that if **n** is composite with prime factor ,
then **q** divides the left side of (4.1) (as **q** divides ),
but not the right side. On the other hand suppose that **n=p** is prime.
We prove (4.1) for by induction on **a**:
For **a=1** this is just Wilson's Theorem.
Thereafter, the ratio of (4.1) for **a+1** to (4.1) for **a**, is
on the left side and
on the right side, which are congruent, modulo **p**, by Fermat's Theorem
and Wilson's Theorem.

Contents