Wilson-Primzahl

Zur Notation siehe Fakultät, Teilbarkeit und Kongruenz

Der Satz von Wilson besagt, dass ${\displaystyle (p-1)!+1}$  genau dann durch ${\displaystyle p}$  teilbar ist, wenn ${\displaystyle p}$  eine Primzahl ist. Für jede Primzahl ${\displaystyle p}$  gilt also:

${\displaystyle p\mid (p-1)!+1}$ 

Als Kongruenz lässt sich dies wie folgt beschreiben:

${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$ 

oder

${\displaystyle (p-1)!+1\equiv 0{\pmod {p}}}$ 

Das ganzzahlige Ergebnis der Division

${\displaystyle {\frac {(p-1)!+1}{p}}}$ 

wird in diesem Zusammenhang auch als Wilson-Quotient ${\displaystyle W(p)}$  bezeichnet^[1] (Folge A007619 in OEIS).

Eine Wilson-Primzahl ist nun jede Primzahl ${\displaystyle p}$ , die darüber hinaus sogar Teiler „ihres“ Wilson-Quotienten ist (und den Satz von Wilson damit quasi zweimal erfüllt).

Ohne Beschränkung der Allgemeinheit sei ${\displaystyle n>2}$ 

• ${\displaystyle n}$  ist ${\displaystyle prim\Rightarrow (n-1)!\equiv -1\mod n}$ 

${\displaystyle \forall a\in \mathbb {Z} _{n}^{*}}$  hat ${\displaystyle ax\equiv 1(\mod n)}$  eine eindeutige Lösung ${\displaystyle a^{-1}\mod n}$ 

${\displaystyle a^{2}\equiv 1\Leftrightarrow (a-1)(a+1)=y\cdot n\Leftrightarrow (a\equiv 1\mod n}$  oder ${\displaystyle -1\mod n)}$ 

${\displaystyle (n-1)!\equiv (n-1)\equiv -1\mod n}$ 

• ${\displaystyle (n-1)!\equiv -1\mod n}$  ${\displaystyle \Rightarrow n}$  ist ${\displaystyle {\text{prim}}}$ 

Annahme: ${\displaystyle n=a\cdot b,a,b>1}$ 

${\displaystyle a{\text{ teilt }}(n-1)!}$  mit ${\displaystyle (n-1)!\equiv -1\mod n\Rightarrow a{\text{ teilt }}n-1}$ 

Widerspruch: ${\displaystyle a}$  kann nicht gleichzeitig ${\displaystyle n}$  und ${\displaystyle n-1}$  teilen

Die Zahl ${\displaystyle p=13}$  ist ein Teiler von ${\displaystyle (p-1)!+1}$ :

${\displaystyle {\frac {(13-1)!+1}{13}}={\frac {479.001.600+1}{13}}=36.846.277}$ 

Also ist ${\displaystyle p=13}$  wegen des Satzes von Wilson eine Primzahl. Da sie ebenfalls ein Teiler des entsprechenden Wilson-Quotienten ist (36.846.277 ${\displaystyle :}$  13 = 2.834.329), ist sie sogar eine Wilson-Primzahl.

Die wiederholte Teilung entspricht der Division durch das Quadrat der Ausgangszahl. Analog zum Satz von Wilson gilt daher, dass jede Primzahl ${\displaystyle p}$  genau dann eine Wilson-Primzahl ist, wenn:

${\displaystyle p^{2}\mid (p-1)!+1}$ 

Beziehungsweise:

${\displaystyle (p-1)!\equiv -1{\pmod {p^{2}}}}$ 

oder

${\displaystyle {\frac {(p-1)!+1}{p}}=W(p)\equiv 0{\pmod {p}}}$ 

Bisher sind nur die Wilson-Primzahlen 5, 13 und 563^[2] bekannt (Folge A007540 in OEIS). Sollten weitere Wilson-Primzahlen existieren, so sind sie größer als ${\displaystyle 2\cdot 10^{13}}$ .^[3] Es wird vermutet, dass unendlich viele Wilson-Primzahlen existieren, und zwar etwa ${\displaystyle \ln(\ln(y)/\ln(x))}$  zwischen ${\displaystyle x}$  und ${\displaystyle y}$ .^[4][5]

Die Verallgemeinerung des Satzes von Wilson besagt, dass eine natürliche Zahl ${\displaystyle p\in \mathbb {N} }$  genau dann eine Primzahl ist, wenn für alle ${\displaystyle 1\leq n\leq p}$  gilt:

${\displaystyle (n-1)!\cdot (p-n)!\equiv (-1)^{n}{\pmod {p}}}$ 

Es ist ${\displaystyle p}$  also eine Primzahl, wenn ${\displaystyle {\frac {(n-1)!\cdot (p-n)!-(-1)^{n}}{p}}}$  ganzzahlig ist.

Eine verallgemeinerte Wilson-Primzahl der Ordnung n ist eine Primzahl ${\displaystyle p}$ , für welche gilt:

${\displaystyle p^{2}}$  ist Teiler von ${\displaystyle (n-1)!\cdot (p-n)!-(-1)^{n}}$  mit ${\displaystyle n\geq 1}$ , ${\displaystyle p\geq n}$ 

Es ist ${\displaystyle p}$  also eine verallgemeinerte Wilson-Primzahl der Ordnung n, wenn ${\displaystyle {\frac {(n-1)!\cdot (p-n)!-(-1)^{n}}{p^{2}}}}$  ganzzahlig ist.

Als Kongruenz lässt sich dies wie folgt beschreiben:

${\displaystyle (n-1)!\cdot (p-n)!\equiv (-1)^{n}{\pmod {p^{2}}}}$ 

oder

${\displaystyle (n-1)!\cdot (p-n)!-(-1)^{n}\equiv 0{\pmod {p^{2}}}}$ 

Es wird vermutet, dass es für jede natürliche Zahl ${\displaystyle n}$  unendlich viele verallgemeinerte Wilson-Primzahlen der Ordnung ${\displaystyle n}$  gibt.

Sei ${\displaystyle p=17\in \mathbb {P} }$  eine Primzahl und ${\displaystyle n=7}$ . Die Quadratzahl ${\displaystyle p^{2}=17^{2}=289}$  ist ein Teiler von ${\displaystyle (n-1)!\cdot (p-n)!-(-1)^{n}=6!\cdot (p-7)!+1}$ :

${\displaystyle {\frac {6!\cdot (17-7)!+1}{17^{2}}}={\frac {720\cdot 3628800+1}{289}}={\frac {2612736001}{289}}=9040609}$ 

Also ist ${\displaystyle p=17}$  ein Teiler des entsprechenden verallgemeinerten Wilson-Quotienten und ist deswegen eine verallgemeinerte Wilson-Primzahl der Ordnung ${\displaystyle n=7}$ .

Der folgenden Tabelle kann man die verallgemeinerten Wilson-Primzahlen der Ordnung ${\displaystyle n}$  entnehmen für ${\displaystyle 1\leq n\leq 30}$ :

Die kleinsten verallgemeinerten Wilson-Primzahlen der Ordnung ${\displaystyle n}$  lauten (bei aufsteigendem ${\displaystyle n=1,2,3,\ldots }$ ):

5, 2, 7, 10429, 5, 11, 17 … (Folge A128666 in OEIS)

Schon die nächste verallgemeinerte Wilson-Primzahl der Ordnung ${\displaystyle n=8}$  ist nicht bekannt, muss aber größer als ${\displaystyle 1{,}4\cdot 10^{7}}$  sein.

Eine Primzahl ${\displaystyle p\in \mathbb {P} }$ , welche die Kongruenz

${\displaystyle (p-1)!\equiv -1+Bp{\pmod {p^{2}}}}$  mit betragsmäßig kleinem ${\displaystyle |B|}$ 

erfüllt, nennt man Fast-Wilson-Primzahl (englisch Near-Wilson primes).

Ist ${\displaystyle B=0}$ , so erhält man ${\displaystyle (p-1)!\equiv -1{\pmod {p^{2}}}}$  und erhält die Wilson-Primzahlen.

Der folgenden Tabelle kann man alle solche Fast-Wilson-Primzahlen entnehmen für ${\displaystyle |B|\leq 100}$  mit ${\displaystyle 10^{6}<p<4\cdot 10^{11}}$ :^[3]

Eine Wilson-Zahl ist eine natürliche Zahl ${\displaystyle n}$ , für welche gilt:

${\displaystyle W(n)\equiv 0{\pmod {n^{2}}}}$ , mit ${\displaystyle W(n)=\prod _{\stackrel {1\leq k\leq n}{\operatorname {ggT} (k,n)=1}}{k}+e}$ 

Dabei ist ${\displaystyle e=1}$  genau dann, wenn ${\displaystyle n}$  eine Primitivwurzel hat, sonst ist ${\displaystyle e=-1}$ .

Für jede natürliche Zahl ${\displaystyle n}$  ist ${\displaystyle W(n)}$  durch ${\displaystyle n}$  teilbar. Den Quotienten ${\displaystyle {\frac {W(n)}{n}}}$  nennt man verallgemeinerter Wilson-Quotient.^[6] Die ersten verallgemeinerte Wilson-Quotienten lauten:

2, 1, 1, 1, 5, 1, 103, 13, 249, 19, 329891, 32, 36846277, 1379, 59793, 126689, 1230752346353, 4727, 336967037143579, 436486, 2252263619, 56815333, 48869596859895986087, 1549256, 1654529071288638505 (Folge A157249 in OEIS)

Ist der verallgemeinerte Wilson-Quotient durch ${\displaystyle n}$  teilbar, erhält man eine Wilson-Zahl. Diese lauten:

1, 5, 13, 563, 5971, 558771, 1964215, 8121909, 12326713, 23025711, 26921605, 341569806, 399292158 (Folge A157250 in OEIS)

Wenn eine Wilson-Zahl ${\displaystyle n}$  prim ist, dann ist ${\displaystyle n}$  eine Wilson-Primzahl. Es gibt 13 Wilson-Zahlen für ${\displaystyle n<5\cdot 10^{8}}$ .

• N. G. W. H. Beeger: Quelques remarques sur les congruences r^p−1 ≡ 1 (mod p²) et (p−1)! ≡ −1 (mod p²). In: The Messenger of Mathematics, 43, 1913–1914, S. 72–84 (französisch) Textarchiv – Internet Archive
• Emma Lehmer: On congruences involving Bernoulli numbers and the quotients of Fermat and Wilson. (PDF; 747 kB) In: Annals of Mathematics, 39, April 1938, S. 350–360 (englisch)
• Paulo Ribenboim: Die Welt der Primzahlen. Geheimnisse und Rekorde. Springer, Berlin 2006, ISBN 3-540-34283-4 (aktualisierte Übersetzung von The little book of bigger primes. Springer, New York 2004)

• Eric W. Weisstein: Wilson Prime. In: MathWorld (englisch).
• Chris K. Caldwell: Wilson prime. The Prime Glossary (englisch).
• Here is the latest update on … – E-Mail von Richard McIntosh an Paul Zimmermann vom 9. März 2004 (englisch)
• Emma Lehmer: On congruences involving Bernoulli numbers and the quotients of Fermat and Wilson. Annals of Mathematics 39 (2), April 1938, S. 350–360, abgerufen am 3. Februar 2020. 
• Distributed search for Wilson primes. mersenneforum.org, abgerufen am 3. Februar 2020. 
• Erna H. Pearson: On the Congruences (p − 1)! ≡ −1 and 2^p−1 ≡ 1 (mod p²). Mathematics of Computation 17, 6. April 1962, S. 194–195, abgerufen am 3. Februar 2020. 

1. ↑ Eric W. Weisstein: Wilson Quotient. In: MathWorld (englisch).
2. ↑ Karl Goldberg: A table of Wilson quotients and the third Wilson prime. In: Journal of the London Mathematical Society, 28, April 1953, S. 252–256 (englisch)
3. ↑ ^{a b} Edgar Costa, Robert Gerbicz, David Harvey: A search for Wilson primes. 27. Oktober 2012, S. 1–25, abgerufen am 1. Februar 2020. 
4. ↑ Richard Crandall, Karl Dilcher, Carl Pomerance: A search for Wieferich and Wilson primes. Mathematics of Computation 66, Januar 1997, S. 433–449 (englisch)
5. ↑ Chris K. Caldwell: Wilson prime. The Prime Glossary (englisch).
6. ↑ Takashi Agoh, Karl Dilcher, Ladislav Skula: Wilson Quotients for composite moduli. Mathematics of Computation 67 (222), April 1998, S. 843–861, abgerufen am 2. Februar 2020.