Wolstenholme's theorem explained

p \geq 5 , the congruence{ 2 p -1 \choose p -1 } \equiv 1 \pmod{p ^{3}} holds, where the parentheses denote a binomial coefficient. For example, with p = 7, this says that 1716 is one more than a multiple of 343. The theorem was first proved by Joseph Wolstenholme in 1862. In 1819, Charles Babbage showed the same congruence modulo p², which holds for p \geq 3 . An equivalent formulation is the congruence{ap \choose bp} \equiv {a \choose b} \pmod{p ^{3}} for p \geq 5 , which is due to Wilhelm Ljunggren (and, in the special case b = 1 , to J. W. L. Glaisher) and is inspired by Lucas' theorem.

No known composite numbers satisfy Wolstenholme's theorem and it is conjectured that there are none (see below). A prime that satisfies the congruence modulo p⁴ is called a Wolstenholme prime (see below).

As Wolstenholme himself established, his theorem can also be expressed as a pair of congruences for (generalized) harmonic numbers:

1+ { 1 \over 2 } + { 1 \over 3 } +...+ { 1 \over p -1 } \equiv 0 \pmod{p ^{2}} ,and 1+ { 1 \over 2 ^{2}+{1} \over 3 ^{2}+...+{1} \over (p -1 ) ^{2}} \equiv 0 \pmod p. (Congruences with fractions make sense, provided that the denominators are coprime to the modulus.)For example, with p=7, the first of these says that the numerator of 49/20 is a multiple of 49, while the second says the numerator of 5369/3600 is a multiple of 7.

Wolstenholme primes

See main article: Wolstenholme prime.

A prime p is called a Wolstenholme prime iff the following condition holds:

{{ 2 p -1 }\choose{p -1 }} \equiv 1 \pmod{p ^{4}.}

If p is a Wolstenholme prime, then Glaisher's theorem holds modulo p⁴. The only known Wolstenholme primes so far are 16843 and 2124679 ; any other Wolstenholme prime must be greater than 10⁹. This result is consistent with the heuristic argument that the residue modulo p⁴ is a pseudo-random multiple of p³. This heuristic predicts that the number of Wolstenholme primes between K and N is roughly ln ln N − ln ln K. The Wolstenholme condition has been checked up to 10⁹, and the heuristic says that there should be roughly one Wolstenholme prime between 10⁹ and 10²⁴. A similar heuristic predicts that there are no "doubly Wolstenholme" primes, for which the congruence would hold modulo p⁵.

A proof of the theorem

There is more than one way to prove Wolstenholme's theorem. Here is a proof that directly establishes Glaisher's version using both combinatorics and algebra.

For the moment let p be any prime, and let a and b be any non-negative integers. Then a set A with ap elements can be divided into a rings of length p, and the rings can be rotated separately. Thus, the a-fold direct sum of the cyclic group of order p acts on the set A, and by extension it acts on the set of subsets of size bp. Every orbit of this group action has p^k elements, where k is the number of incomplete rings, i.e., if there are k rings that only partly intersect a subset B in the orbit. There are

style {a \choose b} orbits of size 1 and there are no orbits of size p. Thus we first obtain Babbage's theorem{ap \choose bp} \equiv {a \choose b} \pmod{p ^{2}.} Examining the orbits of size p², we also obtain{ap \choose bp} \equiv {a \choose b} + {a \choose 2 }\left({ 2 p \choose p} - 2 \right){a -2 \choose b -1 } \pmod{p ^{3}.} Among other consequences, this equation tells us that the case a=2 and b=1 implies the general case of the second form of Wolstenholme's theorem.

Switching from combinatorics to algebra, both sides of this congruence are polynomials in a for each fixed value of b. The congruence therefore holds when a is any integer, positive or negative, provided that b is a fixed positive integer. In particular, if a=-1 and b=1, the congruence becomes

{ - p \choose p} \equiv { -1 \choose 1 } + { -1 \choose 2 }\left({ 2 p \choose p} - 2 \right) \pmod{p ^{3}.} This congruence becomes an equation for style { 2 p \choose p} using the relation{ - p \choose p} = (( -1 ) ^{p})/(2 { 2 p) \choose p}. When p is odd, the relation is3 { 2 p \choose p} \equiv 6 \pmod{p ^{3}.} When p≠3, we can divide both sides by 3 to complete the argument.

A similar derivation modulo p⁴ establishes that

{ap \choose bp} \equiv {a \choose b} \pmod{p ^{4}} for all positive a and b if and only if it holds when a=2 and b=1, i.e., if and only if p is a Wolstenholme prime.

The converse as a conjecture

It is conjectured that ifwhen k=3, then n is prime. The conjecture can be understood by considering k = 1 and 2 as well as 3. When k = 1, Babbage's theorem implies that it holds for n = p² for p an odd prime, while Wolstenholme's theorem implies that it holds for n = p³ for p > 3, and it holds for n = p⁴ if p is a Wolstenholme prime. When k = 2, it holds for n = p² if p is a Wolstenholme prime. These three numbers, 4 = 2², 8 = 2³, and 27 = 3³ are not held for with k = 1, but all other prime square and prime cube are held for with k = 1. Only 5 other composite values (neither prime square nor prime cube) of n are known to hold for with k = 1, they are called Wolstenholme pseudoprimes, they are

27173, 2001341, 16024189487, 80478114820849201, 20378551049298456998947681, ...

The first three are not prime powers, the last two are 16843⁴ and 2124679⁴, 16843 and 2124679 are Wolstenholme primes . Besides, with an exception of 16843² and 2124679², no composites are known to hold for with k = 2, much less k = 3. Thus the conjecture is considered likely because Wolstenholme's congruence seems over-constrained and artificial for composite numbers. Moreover, if the congruence does hold for any particular n other than a prime or prime power, and any particular k, it does not imply that

{an \choose bn} \equiv {a \choose b} \pmod{n ^{k}.} The number of Wolstenholme pseudoprimes up to x is O(x ^{1/2} log ( log (x)) ^{499712} ) , so the sum of reciprocals of those numbers converges. The constant 499712 follows from the existence of only three Wolstenholme pseudoprimes up to 10 ^{12} . The number of Wolstenholme pseudoprimes up to 10 ^{12} should be at least 7 if the sum of its reciprocals diverged, and since this is not satisfied because there are only 3 of them in this range, the counting function of these pseudoprimes is at most O(x ^{1/2} log ( log (x)) ^{C)} for some efficiently computable constant C ; we can take C as 499712 . The constant in the big O notation is also effectively computable in O(x ^{1/2} log ( log (x)) ^{499712} ) .

Generalizations

Leudesdorf has proved that for a positive integer n coprime to 6, the following congruence holds:^[1]

\sum ^{n -1} _{i =1 \atop (i,n) =1} (1)/(i) \equiv 0 \pmod{n ^{2}.}

See also

• Fermat's little theorem
• Wilson's theorem
• Wieferich prime
• Wilson prime
• Wall–Sun–Sun prime
• List of special classes of prime numbers
• Table of congruences

References

• .
• .
• .
• .
• .
• .
• R. Mestrovic, Wolstenholme's theorem: Its Generalizations and Extensions in the last hundred and fifty years (1862—2012).
• .

External links

• The Prime Glossary: Wolstenholme prime
• Status of the search for Wolstenholme primes

Notes and References

1. Leudesdorf. C. . Some results in the elementary theory of numbers . Proc. London Math. Soc. . 20 . 1888 . 199–212 . 10.1112/plms/s1-20.1.199.