Wilson-Primzahl

Wilson-Primzahlen (nach Sir John Wilson) sind Primzahlen <math>p</math>, für die gilt, dass <math>(p-1)! + 1</math> durch <math>p^2</math> 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 <math>(p-1)! + 1</math> genau dann durch <math>p</math> teilbar ist, wenn <math>p</math> eine Primzahl ist. Für jede Primzahl <math>p</math> gilt also:

<math>p \mid (p-1)! + 1</math>

Als Kongruenz lässt sich dies wie folgt beschreiben:

<math>(p-1)!\equiv-1\pmod p</math>

oder

<math>(p-1)! + 1 \equiv 0 \pmod p</math>

Das ganzzahlige Ergebnis der Division

<math>\frac{(p-1)! + 1}{p}</math>

wird in diesem Zusammenhang auch als Wilson-Quotient <math>W(p)</math> bezeichnet<ref>Eric W. Weisstein: Wilson Quotient. In: MathWorld (englisch). </ref> (Folge A007619 in OEIS).

Eine Wilson-Primzahl ist nun jede Primzahl <math>p</math>, 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 <math>n > 2</math>

• <math>n</math> ist <math>prim \Rightarrow (n-1)! \equiv -1 \mod n</math>

<math> \forall a \in \mathbb{Z}_n^* </math> hat <math>ax \equiv 1 \mod n</math> eine eindeutige Lösung <math>a^{-1} \mod n</math>

<math>a^2 \equiv 1 \Leftrightarrow (a-1)(a+1)=y\cdot n \Leftrightarrow ( a \equiv 1 \mod n</math> oder <math> -1 \mod n )</math>

<math>(n-1)!\equiv (n-1) \equiv -1 \mod n</math>

• <math>(n-1)! \equiv -1 \mod n</math> <math> \Rightarrow n</math> ist <math>\text{prim}</math>

Annahme: <math> n=a \cdot b, a,b >1</math>

<math> a \text{ teilt } (n-1)!</math> mit <math>(n-1)! \equiv -1 \mod n \Rightarrow a \text{ teilt } n-1</math>

Widerspruch: <math>a</math> kann nicht gleichzeitig <math>n</math> und <math>n-1</math> teilen

Beispiel

Die Zahl <math>p=13</math> ist ein Teiler von <math>(p-1)! + 1</math>:

<math>\frac{(13-1)! + 1}{13} = \frac{479.001.600 + 1}{13} = 36.846.277</math>

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

<math>p^2 \mid (p-1)! + 1</math>

Beziehungsweise:

<math>(p-1)!\equiv-1\pmod{p^2}</math>

oder

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

Vorkommen

Bisher sind nur die Wilson-Primzahlen 5, 13 und 563<ref>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)</ref> bekannt (Folge A007540 in OEIS). Sollten weitere Wilson-Primzahlen existieren, so sind sie größer als <math>2 \cdot 10^{13}</math>.<ref name="Costa">Edgar Costa, Robert Gerbicz, David Harvey: A search for Wilson primes. 27. Oktober 2012, S. 1–25, abgerufen am 1. Februar 2020. </ref> Es wird vermutet, dass unendlich viele Wilson-Primzahlen existieren, und zwar etwa <math>\ln(\ln(y)/\ln(x))</math> zwischen <math>x</math> und <math>y</math>.<ref name="cdp1997">Richard Crandall, Karl Dilcher, Carl Pomerance: A search for Wieferich and Wilson primes. Mathematics of Computation 66, Januar 1997, S. 433–449 (englisch)</ref><ref>Chris K. Caldwell: Wilson prime. The Prime Glossary (englisch).</ref>

Verallgemeinerungen

Wilson-Primzahlen der Ordnung n

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

<math>(n-1)! \cdot (p-n)! \equiv (-1)^n \pmod p</math>

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

Eine verallgemeinerte Wilson-Primzahl der Ordnung n ist eine Primzahl <math>p</math>, für welche gilt:

<math>p^2</math> ist Teiler von <math>(n-1)! \cdot (p-n)! - (-1)^n</math> mit <math>n \geq 1</math>, <math>p \geq n</math>

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

Als Kongruenz lässt sich dies wie folgt beschreiben:

<math>(n-1)! \cdot (p-n)!\equiv (-1)^n \pmod {p^2}</math>

oder

<math>(n-1)! \cdot (p-n)! - (- 1)^n \equiv 0 \pmod {p^2}</math>

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

Beispiel

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

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

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

Der folgenden Tabelle kann man die verallgemeinerten Wilson-Primzahlen der Ordnung <math>n</math> entnehmen für <math>1 \leq n \leq 30</math>:

<math>n</math> <math>(n-1)! \cdot (p-n)! - (-1)^n</math> Primzahl <math>p</math>, sodass <math>p^2</math> Teiler von <math>(n-1)! \cdot (p-n)! - (-1)^n</math> ist OEIS-Link 1 <math>(p-1)!+1</math> 5, 13, 563 … (Folge A007540 in OEIS) 2 <math>(p-2)!-1</math> 2, 3, 11, 107, 4931 … (Folge A079853 in OEIS) 3 <math>2! \cdot (p-3)!+1</math> 7 … 4 <math>3! \cdot (p-4)!-1</math> 10429 … 5 <math>4! \cdot (p-5)!+1</math> 5, 7, 47 … 6 <math>5! \cdot (p-6)!-1</math> 11 … 7 <math>6! \cdot (p-7)!+1</math> 17 … 8 <math>7! \cdot (p-8)!-1</math> … 9 <math>8! \cdot (p-9)!+1</math> 541 … 10 <math>9! \cdot (p-10)!-1</math> 11, 1109 … 11 <math>10! \cdot (p-11)!+1</math> 17, 2713 … 12 <math>11! \cdot (p-12)!-1</math> … 13 <math>12! \cdot (p-13)!+1</math> 13 … 14 <math>13! \cdot (p-14)!-1</math> … 15 <math>14! \cdot (p-15)!+1</math> 349, 41341 …

<math>n</math> <math>(n-1)! \cdot (p-n)! - (-1)^n</math> Primzahl <math>p</math>, sodass <math>p^2</math> Teiler von <math>(n-1)! \cdot (p-n)! - (-1)^n</math> ist OEIS-Link 16 <math>15! \cdot (p-16)!-1</math> 31 … 17 <math>16! \cdot (p-17)!+1</math> 61, 251, 479 … (Folge A152413 in OEIS) 18 <math>17! \cdot (p-18)!-1</math> 13151527 … 19 <math>18! \cdot (p-19)!+1</math> 71, 621629 … 20 <math>19! \cdot (p-20)!-1</math> 59, 499, 43223 … 21 <math>20! \cdot (p-21)!+1</math> 217369 … 22 <math>21! \cdot (p-22)!-1</math> … 23 <math>22! \cdot (p-23)!+1</math> … 24 <math>23! \cdot (p-24)!-1</math> 47, 3163 … 25 <math>24! \cdot (p-25)!+1</math> … 26 <math>25! \cdot (p-26)!-1</math> 97579 … 27 <math>26! \cdot (p-27)!+1</math> 53 … 28 <math>27! \cdot (p-28)!-1</math> 347, 739399 … 29 <math>28! \cdot (p-29)!+1</math> … 30 <math>29! \cdot (p-30)!-1</math> 137, 1109, 5179 …

Die kleinsten verallgemeinerten Wilson-Primzahlen der Ordnung <math>n</math> lauten (bei aufsteigendem <math>n=1,2,3,\ldots</math>):

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

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

Fast-Wilson-Primzahlen

Eine Primzahl <math>p \in \mathbb P</math>, welche die Kongruenz

<math>(p-1)! \equiv -1+Bp \pmod {p^2}</math> mit betragsmäßig kleinem <math>|B|</math>

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

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

Der folgenden Tabelle kann man alle solche Fast-Wilson-Primzahlen entnehmen für <math>|B| \leq 100</math> mit <math>10^6 < p < 4 \cdot 10^{11}</math>:<ref name="Costa" />

<math>p</math> <math>B</math> 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

<math>p</math> <math>B</math> 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

<math>p</math> <math>B</math> 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

<math>p</math> <math>B</math> 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

<math>p</math> <math>B</math> 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

<math>p</math> <math>B</math> 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

<math>p</math> <math>B</math> 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

<math>p</math> <math>B</math> 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 <math>n</math>, für welche gilt:

<math>W(n) \equiv 0 \pmod {n^2}</math>, mit <math>W(n) = \prod_\stackrel{1 \leq k \leq n}{\operatorname{ggT}(k,n)=1}{k}+e</math>

Dabei ist <math>e=1</math> genau dann, wenn <math>n</math> eine Primitivwurzel hat, sonst ist <math>e=-1</math>.

Für jede natürliche Zahl <math>n</math> ist <math>W(n)</math> durch <math>n</math> teilbar. Den Quotienten <math>\frac{W(n)}{n}</math> nennt man verallgemeinerter Wilson-Quotient.<ref name="Dilcher">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. </ref> 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 <math>n</math> 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 <math>n</math> prim ist, dann ist <math>n</math> eine Wilson-Primzahl. Es gibt 13 Wilson-Zahlen für <math>n < 5 \cdot 10^8</math>.

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

<references />