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{\pmod {p}}

oder

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

Das ganzzahlige Ergebnis der Division

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

wird in diesem Zusammenhang auch als Wilson-Quotient $W(p)$ bezeichnet^[1] (Folge A007619 in 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 -1\mod n$

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

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

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

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

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

$a{\text{ teilt }}(n-1)!$ mit $(n-1)!\equiv -1\mod n\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{\pmod {p^{2}}}

oder

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

Vorkommen

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 $2\cdot 10^{13}$ .^[3] Es wird vermutet, dass unendlich viele Wilson-Primzahlen existieren, und zwar etwa $\ln(\ln(y)/\ln(x))$ zwischen $x$ und $y$ .^[4]^[5]

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\leq n\leq p$ gilt:

(n-1)!\cdot (p-n)!\equiv (-1)^{n}{\pmod {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\geq 1

,

p\geq 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}{\pmod {p^{2}}}

oder

(n-1)!\cdot (p-n)!-(-1)^{n}\equiv 0{\pmod {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\leq n\leq 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 …	(Folge A007540 in OEIS)
2	$(p-2)!-1$	2, 3, 11, 107, 4931 …	(Folge A079853 in 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 …	(Folge A152413 in 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,\ldots$ ):

5, 2, 7, 10429, 5, 11, 17 … (Folge A128666 in 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{\pmod {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{\pmod {p^{2}}}$ und erhält die Wilson-Primzahlen.

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

$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{\pmod {n^{2}}}

, mit

W(n)=\prod _{\stackrel {1\leq k\leq n}{\operatorname {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.^[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 $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 $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) 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)

Weblinks

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.

Einzelnachweise

↑ Eric W. Weisstein: Wilson Quotient. In: MathWorld (englisch).
↑ 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)
↑ ^a ^b Edgar Costa, Robert Gerbicz, David Harvey: A search for Wilson primes. 27. Oktober 2012, S. 1–25, abgerufen am 1. Februar 2020.
↑ Richard Crandall, Karl Dilcher, Carl Pomerance: A search for Wieferich and Wilson primes. Mathematics of Computation 66, Januar 1997, S. 433–449 (englisch)
↑ Chris K. Caldwell: Wilson prime. The Prime Glossary (englisch).
↑ 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.

[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)

[Costa-3] Edgar Costa, Robert Gerbicz, David Harvey: A search for Wilson primes. 27. Oktober 2012, S. 1–25, abgerufen am 1. Februar 2020.

[cdp1997-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).

[Dilcher-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.

[1]

[2]

[3]

[4]

[5]

[6]

formelbasiert	Carol ((2ⁿ − 1)² − 2) \| Doppelte Mersenne (2^{2^p − 1} − 1) \| Fakultät (n! ± 1) \| Fermat (2^2ⁿ + 1) \| Kubisch (x³ − y³)/(x − y) \| Kynea ((2ⁿ + 1)² − 2) \| Leyland (x^y + y^x) \| Mersenne (2^p − 1) \| Mills (A^3ⁿ) \| Pierpont (2^u⋅3^v + 1) \| Primorial (p_n# ± 1) \| Proth (k⋅2ⁿ + 1) \| Pythagoreisch (4n + 1) \| Quartisch (x⁴ + y⁴) \| Thabit (3⋅2ⁿ − 1) \| Wagstaff ((2^p + 1)/3) \| Williams ((b-1)⋅bⁿ − 1) \| Woodall (n⋅2ⁿ − 1)
Primzahlfolgen	Bell \| Fibonacci \| Lucas \| Motzkin \| Pell \| Perrin
eigenschaftsbasiert	Elitär \| Fortunate \| Gut \| Glücklich \| Higgs \| Hochkototient \| Isoliert \| Pillai \| Ramanujan \| Regulär \| Stark \| Stern \| Wall–Sun–Sun \| Wieferich \| Wilson
basisabhängig	Belphegor \| Champernowne \| Dihedral \| Einzigartig \| Fröhlich \| Keith \| Lange \| Minimal \| Mirp \| Permutierbar \| Primeval \| Palindrom \| Repunit-Primzahl ((10ⁿ − 1)/9) \| Schwach \| Smarandache–Wellin \| Strobogrammatisch \| Tetradisch \| Trunkierbar \| Zirkular
basierend auf Tupel	Ausbalanciert (p − n, p, p + n) \| Chen \| Cousin (p, p + 4) \| Cunningham (p, 2p ± 1, …) \| Drilling (p, p + 2 oder p + 4, p + 6) \| Konstellation \| Sexy (p, p + 6) \| Sichere (p, (p − 1)/2) \| Sophie Germain (p, 2p + 1) \| Vierling (p, p + 2, p + 6, p + 8) \| Zwilling (p, p + 2) \| Zwillings-Bi-Kette (n ± 1, 2n ± 1, …)
nach Größe	Titanisch (1.000+ Stellen) \| Gigantisch (10.000+ Stellen) \| Mega (1.000.000+ Stellen) \| Beva (1.000.000.000+ Stellen)

Fahrer / Team für die Suche eingeben:

Fahrer / Team für die Suche eingeben:

Eisspeedway

Wilson-Primzahl

Inhaltsverzeichnis

Definition

Beweis

Beispiel

Vorkommen

Verallgemeinerungen

Wilson-Primzahlen der Ordnung n

Beispiel

Fast-Wilson-Primzahlen

Wilson-Zahlen

Literatur

Weblinks

Einzelnachweise