Wolstenholme's theorem

In mathematics, Wolstenholme's theorem states that for a prime number p ≥ 5, the congruence

:<math>{2p-1 \choose p-1} \equiv 1 \pmod{p^3}</math>

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 ≥ 3. An equivalent formulation is the congruence

:<math>{ap \choose bp} \equiv {a \choose b} \pmod{p^3}</math>

for p ≥ 5, which is due to Wilhelm Ljunggren (and, in the special case b = 1, to J. W. L. Glaisher) and is inspired by Lucas's 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:

:<math>1+{1 \over 2}+{1 \over 3}+\dots+{1 \over p-1} \equiv 0 \pmod{p^2} \mbox{, and}</math>

:<math>1+{1 \over 2^2}+{1 \over 3^2}+\dots+{1 \over (p-1)^2} \equiv 0 \pmod p. </math>

since

:<math>{2p-1 \choose p-1}=\prod_{1\leq k\leq p-1} \frac{2p-k}{k} \equiv 1-2p \sum_{1\leq k\leq p-1} \frac{1}{k} \pmod{p^2}</math>

(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

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

:<math> \equiv 1 \pmod{p^4}.</math>

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 <math>\textstyle {a \choose b}</math> orbits of size 1 and there are no orbits of size p. Thus we first obtain Babbage's theorem

:<math>{ap \choose bp} \equiv {a \choose b} \pmod{p^2}.</math>

Examining the orbits of size p², we also obtain

:<math>{ap \choose bp} \equiv {a \choose b} + {a \choose 2}\left({2p \choose p} - 2\right){a -2 \choose b-1} \pmod{p^3}.</math>

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

:<math>{-p \choose p} \equiv {-1 \choose 1} + {-1 \choose 2}\left({2p \choose p} - 2\right) \pmod{p^3}.</math>

This congruence becomes an equation for <math>\textstyle {2p \choose p}</math> using the relation

:<math>{-p \choose p} = \frac{(-1)^p}2{2p \choose p}.</math>

When p is odd, the relation is

:<math>3{2p \choose p} \equiv 6 \pmod{p^3}.</math>

When p ≠ 3, we can divide both sides by 3 to complete the argument.

A similar derivation modulo p⁴ establishes that

:<math>{ap \choose bp} \equiv {a \choose b} \pmod{p^4}</math>

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 if

when 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

:<math>{an \choose bn} \equiv {a \choose b} \pmod{n^k}.</math>

The number of Wolstenholme pseudoprimes up to x is <math>O(x^{1/2} \log(\log(x))^{499712})</math>, so the sum of reciprocals of those numbers converges. The constant 499712 follows from the existence of only three Wolstenholme pseudoprimes up to 10¹². The number of Wolstenholme pseudoprimes up to 10¹² 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 <math>O(x^{1/2} \log(\log(x))^C)</math> for some efficiently computable constant C; we can take C as 499712. The constant in the big O notation is also effectively computable in <math>O(x^{1/2} \log(\log(x))^{499712})</math>.

Generalizations

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

:<math> \sum_{i=1\atop \gcd(i,n)=1}^{n-1} \frac{1}{i} \equiv 0\pmod{n^2}.</math>

In 1900, Glaisher showed further that: for prime p > 3,

:<math> \binom{2p-1}{p-1} \equiv 1- \frac{2p^3}{3}B_{p-3} \pmod{p^4}.</math>

Where B_n is the Bernoulli number.

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

Notes

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