Wolstenholme's Theorem
   HOME

TheInfoList



OR:

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 : \equiv 1 \pmod 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 : \equiv \pmod 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: :1+++\dots+ \equiv 0 \pmod \mbox :1+++\dots+ \equiv 0 \pmod p. since :=\prod_ \frac \equiv 1-2p \sum_ \frac \pmod (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: : \equiv 1 \pmod. 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 1011. 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 1011, and the heuristic says that there should be roughly one Wolstenholme prime between 1011 and 1024. 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 ''pk'' 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 \textstyle orbits of size 1 and there are no orbits of size ''p''. Thus we first obtain Babbage's theorem : \equiv \pmod. Examining the orbits of size ''p''2, we also obtain : \equiv + \left( - 2\right) \pmod. 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 : \equiv + \left( - 2\right) \pmod. This congruence becomes an equation for \textstyle using the relation : = \frac2. When ''p'' is odd, the relation is :3 \equiv 6 \pmod. When ''p'' ≠ 3, we can divide both sides by 3 to complete the argument. A similar derivation modulo ''p''4 establishes that : \equiv \pmod 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 = 22, 8 = 23, and 27 = 33 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 168434 and 21246794, 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 168432 and 21246792, 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 : \equiv \pmod. The number of Wolstenholme pseudoprimes up to ''x'' is O(x^ \log(\log(x))^), so the sum of reciprocals of those numbers converges. The constant 499712 follows from the existence of only three Wolstenholme pseudoprimes up to 1012. The number of Wolstenholme pseudoprimes up to 1012 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^ \log(\log(x))^C) 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 O(x^ \log(\log(x))^).


Generalizations

Leudesdorf has proved that for a positive integer ''n'' coprime to 6, the following congruence holds: : \sum_^ \frac \equiv 0\pmod. 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, : \binom \equiv 1- \fracB_ \pmod. Where ''Bn'' 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 prime

Status of the search for Wolstenholme primes
Classes of prime numbers Factorial and binomial topics Articles containing proofs Theorems about prime numbers