In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, Wolstenholme's theorem states that for a
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
''p'' ≥ 5, the congruence
:
holds, where the parentheses denote a
binomial coefficient
In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
. 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
Joseph Wolstenholme (30 September 1829 – 18 November 1891) was an United Kingdom, English mathematician.
Wolstenholme was born in Eccles, Greater Manchester, Eccles near Salford, Greater Manchester, Salford, Lancashire, England, the son of a M ...
in 1862. In 1819,
Charles Babbage
Charles Babbage (; 26 December 1791 – 18 October 1871) was an English polymath. A mathematician, philosopher, inventor and mechanical engineer, Babbage originated the concept of a digital programmable computer.
Babbage is considered ...
showed the same congruence modulo ''p''
2, which holds for ''p'' ≥ 3. An equivalent formulation is the congruence
:
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 number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Accordingly it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime numb ...
s satisfy Wolstenholme's theorem and it is conjectured that there are none (see below). A prime that satisfies the congruence modulo ''p''
4 is called a
Wolstenholme prime
In number theory, a Wolstenholme prime is a special type of prime number satisfying a stronger version of Wolstenholme's theorem. Wolstenholme's theorem is a congruence relation satisfied by all prime numbers greater than 3. Wolstenholme primes ...
(see below).
As Wolstenholme himself established, his theorem can also be expressed as a pair of congruences for (generalized)
harmonic number
In mathematics, the -th harmonic number is the sum of the reciprocals of the first natural numbers:
H_n= 1+\frac+\frac+\cdots+\frac =\sum_^n \frac.
Starting from , the sequence of harmonic numbers begins:
1, \frac, \frac, \frac, \frac, \dot ...
s:
:
:
since
:
(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
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either both ...
the following condition holds:
:
If ''p'' is a
Wolstenholme prime
In number theory, a Wolstenholme prime is a special type of prime number satisfying a stronger version of Wolstenholme's theorem. Wolstenholme's theorem is a congruence relation satisfied by all prime numbers greater than 3. Wolstenholme primes ...
, then Glaisher's theorem holds modulo ''p''
4. The only known Wolstenholme primes so far are 16843 and 2124679 ; any other Wolstenholme prime must be greater than 10
11. This result is consistent with the
heuristic argument that the
residue modulo ''p''
4 is a
pseudo-random
A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process. Pseudorandom number generators are often used in computer programming, as tradi ...
multiple of ''p''
3. 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
11, and the heuristic says that there should be roughly one Wolstenholme prime between 10
11 and 10
24. A similar heuristic predicts that there are no "doubly Wolstenholme" primes, for which the congruence would hold modulo ''p''
5.
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
orbits of size 1 and there are no orbits of size ''p''. Thus we first obtain Babbage's theorem
:
Examining the orbits of size ''p''
2, we also obtain
:
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
:
This congruence becomes an equation for
using the relation
:
When ''p'' is odd, the relation is
:
When ''p'' ≠ 3, we can divide both sides by 3 to complete the argument.
A similar derivation modulo ''p''
4 establishes that
:
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''
2 for ''p'' an odd prime, while Wolstenholme's theorem implies that it holds for ''n'' = ''p''
3 for ''p'' > 3, and it holds for ''n'' = ''p''
4 if ''p'' is a Wolstenholme prime. When ''k'' = 2, it holds for ''n'' = ''p''
2 if ''p'' is a Wolstenholme prime. These three numbers, 4 = 2
2, 8 = 2
3, and 27 = 3
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
4 and 2124679
4, 16843 and 2124679 are
Wolstenholme prime
In number theory, a Wolstenholme prime is a special type of prime number satisfying a stronger version of Wolstenholme's theorem. Wolstenholme's theorem is a congruence relation satisfied by all prime numbers greater than 3. Wolstenholme primes ...
s . Besides, with an exception of 16843
2 and 2124679
2, 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
:
The number of Wolstenholme pseudoprimes up to ''x'' is
, 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
for some efficiently computable constant ''C''; we can take ''C'' as 499712. The constant in the
big O notation
Big ''O'' notation is a mathematical notation that describes the asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...
is also effectively computable in
.
Generalizations
Leudesdorf has proved that for a positive integer ''n'' coprime to 6, the following congruence holds:
:
In 1900, Glaisher
[ J.W.L. Glaisher, On the residues of the sums of products of the first ''p'' − 1 numbers, and
their powers, to modulus p2 or p3, Quart. J. Math. 31 (1900), 321–353.] showed further that: for prime ''p'' > 3,
:
Where ''B
n'' is the
Bernoulli number
In mathematics, the Bernoulli numbers are a sequence of rational numbers which occur frequently in analysis. The Bernoulli numbers appear in (and can be defined by) the Taylor series expansions of the tangent and hyperbolic tangent function ...
.
See also
*
Fermat's little theorem
In number theory, Fermat's little theorem states that if is a prime number, then for any integer , the number is an integer multiple of . In the notation of modular arithmetic, this is expressed as
a^p \equiv a \pmod p.
For example, if and , t ...
*
Wilson's theorem
In algebra and number theory, Wilson's theorem states that a natural number ''n'' > 1 is a prime number if and only if the product of all the positive integers less than ''n'' is one less than a multiple of ''n''. That is (using the notations of ...
*
Wieferich prime
In number theory, a Wieferich prime is a prime number ''p'' such that ''p''2 divides , therefore connecting these primes with Fermat's little theorem, which states that every odd prime ''p'' divides . Wieferich primes were first described by A ...
*
Wilson prime
In number theory, a Wilson prime is a prime number p such that p^2 divides (p-1)!+1, where "!" denotes the factorial function; compare this with Wilson's theorem, which states that every prime p divides (p-1)!+1. Both are named for 18th-century ...
*
Wall–Sun–Sun prime
In number theory, a Wall–Sun–Sun prime or Fibonacci–Wieferich prime is a certain kind of prime number which is conjectured to exist, although none are known.
Definition
Let p be a prime number. When each term in the sequence of Fibona ...
*
List of special classes of prime numbers
*
Table of congruences
In number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from int ...
Notes
References
*.
*.
*.
*.
*.
*.
*R. Mestrovic
Wolstenholme's theorem: Its Generalizations and Extensions in the last hundred and fifty years (1862—2012)
*{{Citation , first=Joseph , last=Wolstenholme , title=On certain properties of prime numbers , journal=The Quarterly Journal of Pure and Applied Mathematics , volume=5 , year=1862 , pages=35–39 , url=https://books.google.com/books?id=vL0KAAAAIAAJ&pg=PA35.
External links
The Prime Glossary: Wolstenholme primeStatus of the search for Wolstenholme primes
Classes of prime numbers
Factorial and binomial topics
Articles containing proofs
Theorems about prime numbers