Misplaced Pages

Wolstenholme's theorem: Difference between revisions

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editNext edit →Content deleted Content addedVisualWikitext
Revision as of 10:50, 24 June 2018 editBurrobert (talk | contribs)Extended confirmed users11,343 edits The converse as a conjecture: Used maths templates to refer to equation.Tags: Mobile edit Mobile web edit← Previous edit Revision as of 10:28, 3 September 2018 edit undoXayahrainie43 (talk | contribs)Extended confirmed users2,748 edits The converse as a conjectureNext edit →
Line 54: Line 54:
The first three are not prime powers {{OEIS|id=A228562}}, the last two are 16843<sup>4</sup> and 2124679<sup>4</sup>, 16843 and 2124679 are ]s {{OEIS|id=A088164}}. Besides, with an exception of 16843<sup>2</sup> and 2124679<sup>2</sup>, no composites are known to hold for ({{EquationNote|1}}) 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 first three are not prime powers {{OEIS|id=A228562}}, the last two are 16843<sup>4</sup> and 2124679<sup>4</sup>, 16843 and 2124679 are ]s {{OEIS|id=A088164}}. Besides, with an exception of 16843<sup>2</sup> and 2124679<sup>2</sup>, no composites are known to hold for ({{EquationNote|1}}) 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> :<math>{an \choose bn} \equiv {a \choose b} \pmod{n^k}.</math>

For a special example,

:<math>{2n \choose n} \equiv 2 \pmod{n^k}.</math>

This congruence holds for all (primes, prime squares, or prime cubes) ''n'' (except 8 and 27), but again, there are also other ''n'' hold for this congruence, the smallest such ('''pseudoprime''') ''n'' is 418.


== Generalizations == == Generalizations ==

Revision as of 10:28, 3 September 2018

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

( 2 p 1 p 1 ) 1 ( mod p 3 ) {\displaystyle {2p-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. An equivalent formulation is the congruence

( a p b p ) ( a b ) ( mod p 3 ) . {\displaystyle {ap \choose bp}\equiv {a \choose b}{\pmod {p^{3}}}.}

The theorem was first proved by Joseph Wolstenholme in 1862. In 1819, Charles Babbage showed the same congruence modulo p, which holds for all primes p (for p=2 only in the second formulation). The second formulation of Wolstenholme's theorem is due 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 2 + 1 3 + . . . + 1 p 1 0 ( mod p 2 ) , and {\displaystyle 1+{1 \over 2}+{1 \over 3}+...+{1 \over p-1}\equiv 0{\pmod {p^{2}}}{\mbox{, and}}}
1 + 1 2 2 + 1 3 2 + . . . + 1 ( p 1 ) 2 0 ( mod p ) . {\displaystyle 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

Main article: Wolstenholme prime

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

( 2 p 1 p 1 ) 1 ( mod p 4 ) . {\displaystyle {{2p-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 (sequence A088164 in the OEIS); 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 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 ( a b ) {\displaystyle \textstyle {a \choose b}} orbits of size 1 and there are no orbits of size p. Thus we first obtain Babbage's theorem

( a p b p ) ( a b ) ( mod p 2 ) . {\displaystyle {ap \choose bp}\equiv {a \choose b}{\pmod {p^{2}}}.}

Examining the orbits of size p, we also obtain

( a p b p ) ( a b ) + ( a 2 ) ( ( 2 p p ) 2 ) ( a 2 b 1 ) ( mod p 3 ) . {\displaystyle {ap \choose bp}\equiv {a \choose b}+{a \choose 2}\left({2p \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 p ) ( 1 1 ) + ( 1 2 ) ( ( 2 p p ) 2 ) ( mod p 3 ) . {\displaystyle {-p \choose p}\equiv {-1 \choose 1}+{-1 \choose 2}\left({2p \choose p}-2\right){\pmod {p^{3}}}.}

This congruence becomes an equation for ( 2 p p ) {\displaystyle \textstyle {2p \choose p}} using the relation

( p p ) = ( 1 ) p 2 ( 2 p p ) . {\displaystyle {-p \choose p}={\frac {(-1)^{p}}{2}}{2p \choose p}.}

When p is odd, the relation is

3 ( 2 p p ) 6 ( mod p 3 ) . {\displaystyle 3{2p \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

( a p b p ) ( a b ) ( mod p 4 ) {\displaystyle {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 if

( 2 n 1 n 1 ) 1 ( mod n k ) {\displaystyle {2n-1 \choose n-1}\equiv 1{\pmod {n^{k}}}} 1

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 hold for (1) with k = 1, but all other prime square and prime cube are hold for (1) with k = 1. Only 5 other composite values (neither prime square nor prime cube) of n are known to hold for (1) with k = 1, they are called Wolstenholme pseudoprimes, they are

27173, 2001341, 16024189487, 80478114820849201, 20378551049298456998947681, ... (sequence A082180 in the OEIS)

The first three are not prime powers (sequence A228562 in the OEIS), the last two are 16843 and 2124679, 16843 and 2124679 are Wolstenholme primes (sequence A088164 in the OEIS). Besides, with an exception of 16843 and 2124679, no composites are known to hold for (1) 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

( a n b n ) ( a b ) ( mod n k ) . {\displaystyle {an \choose bn}\equiv {a \choose b}{\pmod {n^{k}}}.}

For a special example,

( 2 n n ) 2 ( mod n k ) . {\displaystyle {2n \choose n}\equiv 2{\pmod {n^{k}}}.}

This congruence holds for all (primes, prime squares, or prime cubes) n (except 8 and 27), but again, there are also other n hold for this congruence, the smallest such (pseudoprime) n is 418.

Generalizations

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

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

See also

Notes

  1. McIntosh, R. J.; Roettger, E. L. (2007), "A search for Fibonacci−Wieferich and Wolstenholme primes", Mathematics of Computation, 76 (260): 2087–2094, CiteSeerX 10.1.1.105.9393, doi:10.1090/S0025-5718-07-01955-2
  2. Leudesdorf, C. (1888). "Some results in the elementary theory of numbers". Proc. London Math. Soc. 20: 199–212. doi:10.1112/plms/s1-20.1.199.

References

External links

Categories: