Wilson-Primzahlen (nach Sir John Wilson) sind Primzahlen
, für die gilt, dass
durch
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
genau dann durch
teilbar ist, wenn
eine Primzahl ist. Für jede Primzahl
gilt also:
![{\displaystyle p\mid (p-1)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c9c9680b694f46f461a105c14780c04d437f79c)
Als Kongruenz lässt sich dies wie folgt beschreiben:
![{\displaystyle (p-1)!\equiv -1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45d18a5a5793c65b8e51e36bac25d0b9e8bfe22c)
oder
![{\displaystyle (p-1)!+1\equiv 0{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15c856d74d3be1912c36e032dade0fffb81851a9)
Das ganzzahlige Ergebnis der Division
![{\displaystyle {\frac {(p-1)!+1}{p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be8112076b480e54a23a7418fd701a142ddd7b70)
wird in diesem Zusammenhang auch als Wilson-Quotient
bezeichnet[1] (Folge A007619 in OEIS).
Eine Wilson-Primzahl ist nun jede Primzahl
, 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
ist ![{\displaystyle prim\Rightarrow (n-1)!\equiv -1\mod n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea96d01d0815d4bb6ee1e7998e9c8e0cae7af9d0)
hat
eine eindeutige Lösung
oder
ist ![{\displaystyle {\text{prim}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6ef62b12a9d9b7600cbe4b38906329e52e6c297)
Annahme:
mit
Widerspruch:
kann nicht gleichzeitig
und
teilen
Beispiel
Die Zahl
ist ein Teiler von
:
![{\displaystyle {\frac {(13-1)!+1}{13}}={\frac {479.001.600+1}{13}}=36.846.277}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43c3d2ac1bf04411cc906f41e62455a9644e3ea4)
Also ist
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
genau dann eine Wilson-Primzahl ist, wenn:
![{\displaystyle p^{2}\mid (p-1)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf3bc2b9833a0df3475aaa3071bce58f5fec39d1)
Beziehungsweise:
![{\displaystyle (p-1)!\equiv -1{\pmod {p^{2}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f89ca2024376626a4fe41c4411a20dd1a323312)
oder
![{\displaystyle {\frac {(p-1)!+1}{p}}=W(p)\equiv 0{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b650f790a2ef660bbcf46476a55fd79192b2fdc1)
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
.[3] Es wird vermutet, dass unendlich viele Wilson-Primzahlen existieren, und zwar etwa
zwischen
und
.[4][5]
Verallgemeinerungen
Wilson-Primzahlen der Ordnung n
Die Verallgemeinerung des Satzes von Wilson besagt, dass eine natürliche Zahl
genau dann eine Primzahl ist, wenn für alle
gilt:
![{\displaystyle (n-1)!\cdot (p-n)!\equiv (-1)^{n}{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b65b0bdd6062f83317968a3417ef38c18bee2c17)
Es ist
also eine Primzahl, wenn
ganzzahlig ist.
Eine verallgemeinerte Wilson-Primzahl der Ordnung n ist eine Primzahl
, für welche gilt:
ist Teiler von
mit
, ![{\displaystyle p\geq n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a51b776df48d590644ebc36a9d846b538c850858)
Es ist
also eine verallgemeinerte Wilson-Primzahl der Ordnung n, wenn
ganzzahlig ist.
Als Kongruenz lässt sich dies wie folgt beschreiben:
![{\displaystyle (n-1)!\cdot (p-n)!\equiv (-1)^{n}{\pmod {p^{2}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7d9a72321c5aad765a883d67a2af4b55b329952)
oder
![{\displaystyle (n-1)!\cdot (p-n)!-(-1)^{n}\equiv 0{\pmod {p^{2}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a786319720021c1410bd817217d2b07fbd54982d)
Es wird vermutet, dass es für jede natürliche Zahl
unendlich viele verallgemeinerte Wilson-Primzahlen der Ordnung
gibt.
Beispiel
Sei
eine Primzahl und
. Die Quadratzahl
ist ein Teiler von
:
![{\displaystyle {\frac {6!\cdot (17-7)!+1}{17^{2}}}={\frac {720\cdot 3628800+1}{289}}={\frac {2612736001}{289}}=9040609}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13fec3999b69b05cfa6f2db35210e016b27a0708)
Also ist
ein Teiler des entsprechenden verallgemeinerten Wilson-Quotienten und ist deswegen eine verallgemeinerte Wilson-Primzahl der Ordnung
.
Der folgenden Tabelle kann man die verallgemeinerten Wilson-Primzahlen der Ordnung
entnehmen für
:
| | Primzahl , sodass Teiler von ist | OEIS-Link | 1 | ![{\displaystyle (p-1)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8cfd25ee2b763467e4925821e3cfc9a365d7b5e4) | 5, 13, 563 … | (Folge A007540 in OEIS) | 2 | ![{\displaystyle (p-2)!-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b1e56bd5c71f8571f85c31ba89160356d43465b) | 2, 3, 11, 107, 4931 … | (Folge A079853 in OEIS) | 3 | ![{\displaystyle 2!\cdot (p-3)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b840c2ec2bf1271bb2e71a2978b96278a4ce1511) | 7 … | | 4 | ![{\displaystyle 3!\cdot (p-4)!-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/244a4d959249ee27c7e512f2b52cbcf44ce13148) | 10429 … | | 5 | ![{\displaystyle 4!\cdot (p-5)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6accae85a670f7fa645aae082c8400f08c8fa53) | 5, 7, 47 … | | 6 | ![{\displaystyle 5!\cdot (p-6)!-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/922ede4d3aa8c70596b54d19fcf483b45befa54e) | 11 … | | 7 | ![{\displaystyle 6!\cdot (p-7)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cae8f042010f4eada5c9f3fad5e4b5720d8f2fc0) | 17 … | | 8 | ![{\displaystyle 7!\cdot (p-8)!-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fef0c261cf6cc3f6902cbf038bdce0156381fdcd) | … | | 9 | ![{\displaystyle 8!\cdot (p-9)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bde38c457c28d76fe9c61057eb3d89f7f22917e6) | 541 … | | 10 | ![{\displaystyle 9!\cdot (p-10)!-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7cd98d2cc474e63e85355fb5cd015dd963a46552) | 11, 1109 … | | 11 | ![{\displaystyle 10!\cdot (p-11)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d5adadf30e16ca27d98fdfa041c48825524b593) | 17, 2713 … | | 12 | ![{\displaystyle 11!\cdot (p-12)!-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05e18c9185276a1c255129c0be3b36ea114b8358) | … | | 13 | ![{\displaystyle 12!\cdot (p-13)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cad56e2bea5ae00512c98cb2b441cbd7b481921c) | 13 … | | 14 | ![{\displaystyle 13!\cdot (p-14)!-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4b63e40f353bc0583e6c7782f09bc2d4577cd92) | … | | 15 | ![{\displaystyle 14!\cdot (p-15)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e884a3ec8c5c293e1c3dac5df10a7af86eeeefe) | 349 … | | | | | Primzahl , sodass Teiler von ist | OEIS-Link | 16 | ![{\displaystyle 15!\cdot (p-16)!-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96567eeb4a1c6508ec892bf67d4d46d03fddfbe7) | 31 … | | 17 | ![{\displaystyle 16!\cdot (p-17)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97e0439849bc515712abfdfec44923d1b531e347) | 61, 251, 479 … | (Folge A152413 in OEIS) | 18 | ![{\displaystyle 17!\cdot (p-18)!-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3977555a1148bfcc696e32698c79a56cd2279cf2) | 13151527 … | | 19 | ![{\displaystyle 18!\cdot (p-19)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2fa9e67188e2140450ad2eae0c094c7214713d2f) | 71 … | | 20 | ![{\displaystyle 19!\cdot (p-20)!-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/057b2aad7491f3ba84b8a670692332ec08223033) | 59, 499 … | | 21 | ![{\displaystyle 20!\cdot (p-21)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f06d5a0d12d026c8fb170f57965a38b50739720b) | 217369 … | | 22 | ![{\displaystyle 21!\cdot (p-22)!-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25bbc39edf50b59b643e0190398f57885c7577b1) | … | | 23 | ![{\displaystyle 22!\cdot (p-23)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fecc1f9af8a38061203c17d16d0a76a1998b47e9) | … | | 24 | ![{\displaystyle 23!\cdot (p-24)!-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3ea3d560a0dbd8c0118f7562e68b752ba60a5598) | 47, 3163 … | | 25 | ![{\displaystyle 24!\cdot (p-25)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f523d648766039640b9451416f0250e5208edd0d) | … | | 26 | ![{\displaystyle 25!\cdot (p-26)!-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41059a777fc5a4e294c710d39969c0626ecbd547) | 97579 … | | 27 | ![{\displaystyle 26!\cdot (p-27)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b2a013645d6a12f7bd0d3a18045593de2d13c08) | 53 … | | 28 | ![{\displaystyle 27!\cdot (p-28)!-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/545e064bf0ab4e2fcf46ecc27e3a2872fd2f2456) | 347 … | | 29 | ![{\displaystyle 28!\cdot (p-29)!+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/340ef7c3ac4ccfcb2f34fc1cbfbfac313b4720a2) | … | | 30 | ![{\displaystyle 29!\cdot (p-30)!-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91b4707259ecf6710c0e5fd11babf6e839bd829f) | 137, 1109, 5179 … | | |
Die kleinsten verallgemeinerten Wilson-Primzahlen der Ordnung
lauten (bei aufsteigendem
):
- 5, 2, 7, 10429, 5, 11, 17 … (Folge A128666 in OEIS)
Schon die nächste verallgemeinerte Wilson-Primzahl der Ordnung
ist nicht bekannt, muss aber größer als
sein.
Fast-Wilson-Primzahlen
Eine Primzahl
, welche die Kongruenz
mit betragsmäßig kleinem ![{\displaystyle |B|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/09a17e400743ffd99fb026d81d8298a6e6344352)
erfüllt, nennt man Fast-Wilson-Primzahl (englisch Near-Wilson primes).
Ist
, so erhält man
und erhält die Wilson-Primzahlen.
Der folgenden Tabelle kann man alle solche Fast-Wilson-Primzahlen entnehmen für
mit
:[3]
| | 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 | | | | 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 | | | | 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 | | | | 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 | | | | 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 | | | | 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 | | | | 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 | | | | 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
, für welche gilt:
, mit ![{\displaystyle W(n)=\prod _{\stackrel {1\leq k\leq n}{\operatorname {ggT} (k,n)=1}}{k}+e}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac9e5f268e142301b04fc001fcb0aad15a6f47d9)
Dabei ist
genau dann, wenn
eine Primitivwurzel hat, sonst ist
.
Für jede natürliche Zahl
ist
durch
teilbar. Den Quotienten
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
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
prim ist, dann ist
eine Wilson-Primzahl. Es gibt 13 Wilson-Zahlen für
.
Literatur
- N. G. W. H. Beeger: Quelques remarques sur les congruences rp−1 ≡ 1 (mod p2) et (p−1)! ≡ −1 (mod p2). 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 2p−1 ≡ 1 (mod p2). 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.
formelbasiert | Carol ((2n − 1)2 − 2) | Doppelte Mersenne (22p − 1 − 1) | Fakultät (n! ± 1) | Fermat (22n + 1) | Kubisch (x3 − y3)/(x − y) | Kynea ((2n + 1)2 − 2) | Leyland (xy + yx) | Mersenne (2p − 1) | Mills (A3n) | Pierpont (2u⋅3v + 1) | Primorial (pn# ± 1) | Proth (k⋅2n + 1) | Pythagoreisch (4n + 1) | Quartisch (x4 + y4) | Thabit (3⋅2n − 1) | Wagstaff ((2p + 1)/3) | Williams ((b-1)⋅bn − 1) | Woodall (n⋅2n − 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 ((10n − 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) |