In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, 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 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 because the only ways ...
, 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 English mathematician.
Wolstenholme was born in Eccles near Salford, Lancashire, England, the son of a Methodist minister, Joseph Wolstenholme, and his wife, Elizabeth, ''née' ...
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
. An equivalent formulation is the congruence
:
for
, which is due to
Wilhelm Ljunggren
Wilhelm Ljunggren (7 October 1905 – 25 January 1973) was a Norwegian mathematician, specializing in number theory..
Career
Ljunggren was born in Kristiania and finished his secondary education in 1925. He studied at the University of Oslo, ear ...
(and, in the special case
, to
J. W. L. Glaisher) and is inspired by
Lucas' theorem
In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient \tbinom by a prime number ''p'' in terms of the radix, base ''p'' expansions of the integers ''m'' and ''n''.
Lucas's theorem first appeared in 1878 ...
.
No known
composite number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
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 (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:
:
:
(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" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicon ...
the following condition holds:
:
If ''p'' is a
Wolstenholme prime, 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
9. This result is consistent with the
heuristic argument
A heuristic argument is an argument that reasons from the value of a method or principle that has been shown experimentally (especially through trial-and-error) to be useful or convincing in learning, discovery and problem-solving, but whose line ...
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.
Background
The generation of random numbers has many uses, such as for rando ...
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
9, and the heuristic says that there should be roughly one Wolstenholme prime between 10
9 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 primes . 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
is
, so the sum of reciprocals of those numbers converges. The constant
follows from the existence of only three Wolstenholme pseudoprimes up to
. The number of Wolstenholme pseudoprimes up to
should be at least 7 if the sum of its reciprocals diverged, and since this is not satisfied, the counting function of these pseudoprimes is at most
for some efficiently computable constant
; we can take
as 499712.
Generalizations
Leudesdorf has proved that for a positive integer ''n'' coprime to 6, the following congruence holds:
:
See also
*
Fermat's little theorem
Fermat's little theorem states that if ''p'' is a prime number, then for any integer ''a'', the number a^p - a is an integer multiple of ''p''. In the notation of modular arithmetic, this is expressed as
: a^p \equiv a \pmod p.
For example, if = ...
*
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 m ...
*
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 Ar ...
*
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 E ...
*
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 Fibonac ...
*
List of special classes of prime numbers
*
Table of congruences In mathematics, a congruence is an equivalence relation on the integers. The following sections list important or interesting prime-related congruences.
Table of congruences characterizing special primes
Other prime-related congruences
There ...
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