help annotate
Contents Next: Pascal's triangle via Up: Arithmetic Properties of Binomial Previous: Binomial coefficients modulo

Recognizing the primes.

[Annotate][Shownotes]


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 if n divides .

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 if m divides 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 and n, free of prime factors , we have that n is 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.



help annotate
Contents Next: Pascal's triangle via Up: Arithmetic Properties of Binomial Previous: Binomial coefficients modulo