Wilson-Primzahl

Wilson-Primzahlen (nach Sir John Wilson) sind Primzahlen $p$, für die gilt, dass $(p-1)!+1$ durch $p^2$ teilbar ist. Es handelt sich dabei um eine stärkere Form des Satzes von Wilson. Bisher sind nur die Wilson-Primzahlen 5, 13 und 563 bekannt.

Definition

Zur Notation siehe Fakultät, Teilbarkeit und Kongruenz

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

$p\mid (p-1)!+1$

Als Kongruenz lässt sich dies wie folgt beschreiben:

$(p-1)!\equiv -1(\mathrm{mod}p)$

oder

$(p-1)!+1\equiv 0(\mathrm{mod}p)$

Das ganzzahlige Ergebnis der Division

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

wird in diesem Zusammenhang auch als Wilson-Quotient $W(p)$ bezeichnet (Vorlage:OEIS).

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

Beweis

Ohne Beschränkung der Allgemeinheit sei $n>2$

• $n$ ist $prim\Rightarrow (n-1)!\equiv -1modn$

$\mathrm{\forall }a\in {\mathbb{Z}}_n^{*}$ hat $ax\equiv 1(modn)$ eine eindeutige Lösung $a^{-1}modn$

$a^2\equiv 1\iff (a-1)(a+1)=y\cdot n\iff (a\equiv 1modn$ oder $-1modn)$

$(n-1)!\equiv (n-1)\equiv -1modn$

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

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

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

Widerspruch: $a$ kann nicht gleichzeitig $n$ und $n-1$ teilen

Beispiel

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

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

Also ist $p=13$ wegen des Satzes von Wilson eine Primzahl. Da sie ebenfalls ein Teiler des entsprechenden Wilson-Quotienten ist (36.846.277 $:$ 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 $p$ genau dann eine Wilson-Primzahl ist, wenn:

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

Beziehungsweise:

$(p-1)!\equiv -1(\mathrm{mod}{p}^2)$

oder

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

Vorkommen

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

Verallgemeinerungen

Wilson-Primzahlen der Ordnung n

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

$(n-1)!\cdot (p-n)!\equiv (-1{)}^n(\mathrm{mod}p)$

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

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

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

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

Als Kongruenz lässt sich dies wie folgt beschreiben:

$(n-1)!\cdot (p-n)!\equiv (-1{)}^n(\mathrm{mod}{p}^2)$

oder

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

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

Beispiel

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

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

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

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

$n$ $(n-1)!\cdot (p-n)!-(-1{)}^n$ Primzahl $p$, sodass $p^2$ Teiler von $(n-1)!\cdot (p-n)!-(-1{)}^n$ ist OEIS-Link 1 $(p-1)!+1$ 5, 13, 563 … (Vorlage:OEIS) 2 $(p-2)!-1$ 2, 3, 11, 107, 4931 … (Vorlage:OEIS) 3 $2!\cdot (p-3)!+1$ 7 … 4 $3!\cdot (p-4)!-1$ 10429 … 5 $4!\cdot (p-5)!+1$ 5, 7, 47 … 6 $5!\cdot (p-6)!-1$ 11 … 7 $6!\cdot (p-7)!+1$ 17 … 8 $7!\cdot (p-8)!-1$ … 9 $8!\cdot (p-9)!+1$ 541 … 10 $9!\cdot (p-10)!-1$ 11, 1109 … 11 $10!\cdot (p-11)!+1$ 17, 2713 … 12 $11!\cdot (p-12)!-1$ … 13 $12!\cdot (p-13)!+1$ 13 … 14 $13!\cdot (p-14)!-1$ … 15 $14!\cdot (p-15)!+1$ 349 …

$n$ $(n-1)!\cdot (p-n)!-(-1{)}^n$ Primzahl $p$, sodass $p^2$ Teiler von $(n-1)!\cdot (p-n)!-(-1{)}^n$ ist OEIS-Link 16 $15!\cdot (p-16)!-1$ 31 … 17 $16!\cdot (p-17)!+1$ 61, 251, 479 … (Vorlage:OEIS) 18 $17!\cdot (p-18)!-1$ 13151527 … 19 $18!\cdot (p-19)!+1$ 71 … 20 $19!\cdot (p-20)!-1$ 59, 499 … 21 $20!\cdot (p-21)!+1$ 217369 … 22 $21!\cdot (p-22)!-1$ … 23 $22!\cdot (p-23)!+1$ … 24 $23!\cdot (p-24)!-1$ 47, 3163 … 25 $24!\cdot (p-25)!+1$ … 26 $25!\cdot (p-26)!-1$ 97579 … 27 $26!\cdot (p-27)!+1$ 53 … 28 $27!\cdot (p-28)!-1$ 347 … 29 $28!\cdot (p-29)!+1$ … 30 $29!\cdot (p-30)!-1$ 137, 1109, 5179 …

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

5, 2, 7, 10429, 5, 11, 17 … (Vorlage:OEIS)

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

Fast-Wilson-Primzahlen

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

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

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

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

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

$p$ $B$ 1282279 +20 1306817 −30 1308491 −55 1433813 −32 1638347 −45 1640147 −88 1647931 +14 1666403 +99 1750901 +34 1851953 −50 2031053 −18 2278343 +21 2313083 +15 2695933 −73 3640753 +69 3677071 −32

$p$ $B$ 3764437 −99 3958621 +75 5062469 +39 5063803 +40 6331519 +91 6706067 +45 7392257 +40 8315831 +3 8871167 −85 9278443 −75 9615329 +27 9756727 +23 10746881 −7 11465149 −62 11512541 −26 11892977 −7

$p$ $B$ 12632117 −27 12893203 −53 14296621 +2 16711069 +95 16738091 +58 17879887 +63 19344553 −93 19365641 +75 20951477 +25 20972977 +58 21561013 −90 23818681 +23 27783521 −51 27812887 +21 29085907 +9 29327513 +13

$p$ $B$ 30959321 +24 33187157 +60 33968041 +12 39198017 −7 45920923 −63 51802061 +4 53188379 −54 56151923 −1 57526411 −66 64197799 +13 72818227 −27 87467099 −2 91926437 −32 92191909 +94 93445061 −30 93559087 −3

$p$ $B$ 94510219 −69 101710369 −70 111310567 +22 117385529 −43 176779259 +56 212911781 −92 216331463 −36 253512533 +25 282361201 +24 327357841 −62 411237857 −84 479163953 −50 757362197 −28 824846833 +60 866006431 −81 1227886151 −51

$p$ $B$ 1527857939 −19 1636804231 +64 1686290297 +18 1767839071 +8 1913042311 −65 1987272877 +5 2100839597 −34 2312420701 −78 2476913683 +94 3542985241 −74 4036677373 −5 4271431471 +83 4296847931 +41 5087988391 +51 5127702389 +50 7973760941 +76

$p$ $B$ 9965682053 −18 10242692519 −97 11355061259 −45 11774118061 −1 12896325149 +86 13286279999 +52 20042556601 +27 21950810731 +93 23607097193 +97 24664241321 +46 28737804211 −58 35525054743 +26 41659815553 +55 42647052491 +10 44034466379 +39 60373446719 −48

$p$ $B$ 64643245189 −21 66966581777 +91 67133912011 +9 80248324571 +46 80908082573 −20 100660783343 +87 112825721339 +70 231939720421 +41 258818504023 +4 260584487287 −52 265784418461 −78 298114694431 +82

Wilson-Zahlen

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

$W(n)\equiv 0(\mathrm{mod}{n}^2)$, mit $W(n)=\prod _{\stackrel{1\le k\le n}{\mathrm{ggT}(k,n)=1}}k+e$

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

Für jede natürliche Zahl $n$ ist $W(n)$ durch $n$ teilbar. Den Quotienten $\frac{W(n)}{n}$ nennt man verallgemeinerter Wilson-Quotient. 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 (Vorlage:OEIS)

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

1, 5, 13, 563, 5971, 558771, 1964215, 8121909, 12326713, 23025711, 26921605, 341569806, 399292158 (Vorlage:OEIS)

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

Literatur

• 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) Vorlage:Archive.org
• 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)

Weblinks

• Vorlage:MathWorld
• 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)
• Vorlage:Internetquelle
• Vorlage:Internetquelle
• Vorlage:Internetquelle