Вагстафф Прайм

Вагстафф Прайм
Назван в честь	Сэмюэл С. Вагстафф-младший
Год публикации	1989
Автор публикации	Бейтман, ПТ , Селфридж, Дж.Л. , Вагстафф-младший, СС
Количество известных терминов	44
Первые сроки	3 , 11 , 43 , 683
Самый большой известный термин	(2 138937 +1)/3
ОЭИС Индекс	А000979 ; Простые числа Вагстаффа: простые числа формы (2^p + 1)/3 ;

В теории чисел называется простым числом Вагстафа простое число вида

{{2^{p}+1} \over 3}

где p — нечетное простое число. Простые числа Вагстаффа названы в честь математика Сэмюэля С. Вагстаффа-младшего ; Главные страницы отдают должное Франсуа Морену за то, что он назвал их в лекции на конференции Eurocrypt 1990 года. Простые числа Вагстаффа появляются в гипотезе Нью-Мерсенна и имеют приложения в криптографии .

Примеры [ править ]

Первые три простых числа Вагстафа — 3, 11 и 43, потому что

{\begin{aligned}3&={2^{3}+1 \over 3},\\[5pt]11&={2^{5}+1 \over 3},\\[5pt]43&={2^{7}+1 \over 3}.\end{aligned}}

Вагстафа Известные простые числа

Первые несколько простых чисел Вагстафа:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, … (последовательность A000979 в OEIS )

По состоянию на октябрь 2023 г. ^[update], известные показатели степени, которые производят простые числа Вагстаффа или вероятные простые числа :

3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239, 127031, 138937 ^[2] (все известные простые числа Вагстафа)

141079, 267017, 269987, 374321, 986191, 4031399, …, 13347311, 13372531, 15135397 (вероятные простые числа Вагстаффа) (последовательность A000978 в OEIS )

В феврале 2010 года Тони Рейкс обнаружил вероятное простое число Вагстаффа:

{\frac {2^{4031399}+1}{3}}

которое имеет 1 213 572 цифры и было третьим по величине вероятным простым числом, когда-либо найденным на тот момент. ^[3]

В сентябре 2013 года Райан Проппер объявил об открытии двух дополнительных возможных простых чисел Вагстаффа: ^[4]

{\frac {2^{13347311}+1}{3}}

и

{\frac {2^{13372531}+1}{3}}

Каждое из них представляет собой вероятное простое число с чуть более чем 4 миллионами десятичных цифр. В настоящее время неизвестно, существуют ли показатели степени между 4031399 и 13347311, которые дают вероятные простые числа Вагстафа.

В июне 2021 года Райан Проппер объявил об открытии вероятного простого числа Вагстаффа: ^[5]

{\frac {2^{15135397}+1}{3}}

которое, вероятно, является простым числом с чуть более чем 4,5 миллионами десятичных цифр.

Тестирование на примитивность [ править ]

Простота была доказана или опровергнута для значений p до 138937. Те, у кого p > 138937, являются вероятными простыми числами по состоянию на октябрь 2023 г. ^[ref]. Доказательство простоты для p = 42737 было выполнено Франсуа Мореном в 2007 году с использованием распределенной реализации ECPP , работающей на нескольких сетях рабочих станций в течение 743 ГГц-дней на процессоре Opteron . ^[6] Это было третье по величине доказательство простоты ECPP с момента его открытия до марта 2009 года. ^[7]

Обобщения [ править ]

Естественно рассмотреть ^[8] в более общем смысле числа вида

Q(b,n)={\frac {b^{n}+1}{b+1}}

где база $b\geq 2$ . Поскольку для $n$ странно, что у нас есть

{\frac {b^{n}+1}{b+1}}={\frac {(-b)^{n}-1}{(-b)-1}}=R_{n}(-b)

эти числа называются «базой чисел Вагстаффа». $b$ ", и иногда считается ^[9] случай повторяющихся чисел с отрицательным основанием $-b$ .

Для некоторых конкретных значений $b$ , все $Q(b,n)$ (за возможным исключением очень маленьких $n$ ) являются составными из-за «алгебраической» факторизации. В частности, если $b$ имеет вид совершенной степени с нечетным показателем (например, 8, 27, 32, 64, 125, 128, 216, 243, 343, 512, 729, 1000 и т. д. (последовательность A070265 в OEIS )), то факт что $x^{m}+1$ , с $m$ нечетное, делится на $x+1$ показывает, что $Q(a^{m},n)$ делится на $a^{n}+1$ в этих особых случаях. Другой случай $b=4k^{4}$ , где k - положительное целое число (например, 4, 64, 324, 1024, 2500, 5184 и т. д. (последовательность A141046 в OEIS )), где мы имеем факторизацию Аурифейля .

Однако, когда $b$ не допускает алгебраической факторизации, предполагается , что бесконечное число $n$ ценности делают $Q(b,n)$ премьер, обратите внимание на все $n$ являются нечетными простыми числами.

Для $b=10$ , сами простые числа имеют следующий вид: 9091, 909091, 909090909090909091, 909090909090909090909090909091, … (последовательность A097209 в OEIS ), и эти n s: 5, 7, 19, 31, 53, 6 7, 293, 641, 2137, 3011, 268207, ... (последовательность A001562 в OEIS ).

См. Repunit#Repunit primes для списка обобщенной базы простых чисел Вагстаффа. $b$ . (Обобщенная база простых чисел Вагстафа $b$ являются обобщенной базой простых чисел повторения $-b$ со странным $n$ )

Наименьшие простые числа p такие, что $Q(n,p)$ является простым числом (начинается с n = 2, 0, если такого p не существует)

3, 3, 3, 5, 3, 3, 0, 3, 5, 5, 5, 3, 7, 3, 3, 7, 3, 17, 5, 3, 3, 11, 7, 3, 11, 0, 3, 7, 139, 109, 0, 5, 3, 11, 31, 5, 5, 3, 53, 17, 3, 5, 7, 103, 7, 5, 5, 7, 1153, 3, 7, 21943, 7, 3, 37, 53, 3, 17, 3, 7, 11, 3, 0, 19, 7, 3, 757, 11, 3, 5, 3, ... (последовательность A084742 в ОЭИС )

Наименьшие основания b такие, что $Q(b,prime(n))$ является простым (начинается с n = 2)

2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, ... (последовательность A103795 в OEIS )

Ссылки [ править ]

^ Бейтман, Пенсильвания ; Селфридж, JL ; Вагстафф-младший, СС (1989). «Новая гипотеза Мерсенна». Американский математический ежемесячник . 96 : 125–128. дои : 10.2307/2323195 . JSTOR 2323195 .
^ «Двадцатка лучших: Вагстафф» .
^ «Лучшие рекорды PRP Анри и Рено Лифшицев» . www.primenumbers.net . Проверено 13 ноября 2021 г.
^ Новые представители Wagstaff PRP , mersenneforum.org
^ Объявление о новом PRP Wagstaff , mersenneforum.org
^ Комментарий Франсуа Морена, The Prime Database: (2 ⁴²⁷³⁷ + 1)/3 на The Prime Pages .
^ Колдуэлл, Крис, «Двадцать лучших: доказательство простоты эллиптической кривой» , The Prime Pages
^ Дубнер, Х. и Гранлунд, Т.: Простые числа формы (б ^н + 1)/(b + 1) , Журнал целочисленных последовательностей , Vol. 3 (2000)
^ Repunit , Wolfram MathWorld (Эрик В. Вайсштейн)

Внешние ссылки [ править ]

Джон Ренце и Эрик В. Вайсштейн . «Вагстафф Прайм» . Математический мир .
Крис Колдуэлл, Двадцатка лучших: Вагстафф на сайте Prime Pages .
Рено Лифшиц, «Эффективный вероятный тест простых чисел для чисел вида (2 ^п + 1)/3" .
Тони Рейкс, «Три гипотезы о проверке простоты чисел Мерсенна, Вагстаффа и Ферма на основе циклов орграфа при x ² − 2 по модулю простого числа» .
Список реюнитов в базе от -50 до 50
Список простых чисел Вагстаффа по основанию от 2 до 160

[1] Бейтман, Пенсильвания ; Селфридж, JL ; Вагстафф-младший, СС (1989). «Новая гипотеза Мерсенна». Американский математический ежемесячник . 96 : 125–128. дои : 10.2307/2323195 . JSTOR 2323195 .

[top20-2] «Двадцатка лучших: Вагстафф» .

[3] «Лучшие рекорды PRP Анри и Рено Лифшицев» . www.primenumbers.net . Проверено 13 ноября 2021 г.

[4] Новые представители Wagstaff PRP , mersenneforum.org

[5] Объявление о новом PRP Wagstaff , mersenneforum.org

[6] Комментарий Франсуа Морена, The Prime Database: (2 ⁴²⁷³⁷ + 1)/3 на The Prime Pages .

[7] Колдуэлл, Крис, «Двадцать лучших: доказательство простоты эллиптической кривой» , The Prime Pages

[8] Дубнер, Х. и Гранлунд, Т.: Простые числа формы (б ^н + 1)/(b + 1) , Журнал целочисленных последовательностей , Vol. 3 (2000)

[9] Repunit , Wolfram MathWorld (Эрик В. Вайсштейн)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

v т и Классы простых чисел
By formula	Fermat ( $2 2 n + 1$ ) Mersenne ( $2 p - 1$ ) Double Mersenne ( $2 2 p -1 - 1$ ) Wagstaff $(2 p + 1)/3$ Proth ( $k \cdot2 n + 1$ ) Factorial ( $n! \pm 1$ ) Primorial ( $p n # \pm 1$ ) Euclid ( $p n # + 1$ ) Pythagorean ( $4 n + 1$ ) Pierpont ( $2 m \cdot3 n + 1$ ) Quartan ( $x 4 + y 4$ ) Solinas ( $2 m \pm 2 n \pm 1$ ) Cullen ( $n \cdot2 n + 1$ ) Woodall ( $n \cdot2 n - 1$ ) Cuban ( $x 3 - y 3)/(x - y$ ) Leyland ( $x y + y x$ ) Thabit ( $3\cdot2 n - 1$ ) Williams ( $(b -1)\cdot b n - 1$ ) Mills ( $⌊ A 3 n ⌋$ )
By integer sequence	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin
By property	Wieferich (pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient Unique
Base-dependent	Palindromic Emirp Repunit $(10 n - 1)/9$ Permutable Circular Truncatable Minimal Delicate Primeval Full reptend Unique Happy Self Smarandache–Wellin Strobogrammatic Dihedral Tetradic
Patterns	Twin ( $p, p + 2$ ) Bi-twin chain ( $n \pm 1, 2 n \pm 1, 4 n \pm 1, \dots$ ) Triplet ( $p, p + 2 or p + 4, p + 6$ ) Quadruplet ( $p, p + 2, p + 6, p + 8$ ) k-tuple Cousin ( $p, p + 4$ ) Sexy ( $p, p + 6$ ) Chen Sophie Germain/Safe ( $p, 2 p + 1$ ) Cunningham ( $p, 2 p \pm 1, 4 p \pm 3, 8 p \pm 7, ...$ ) Arithmetic progression ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Balanced ( $consecutive p - n, p, p + n$ )
By size	Mega (1,000,000+ digits) Largest known list
Complex numbers	Eisenstein prime Gaussian prime
Composite numbers	Pseudoprime Catalan Elliptic Euler Euler–Jacobi Fermat Frobenius Lucas Perrin Somer–Lucas Strong Carmichael number Almost prime Semiprime Sphenic number Interprime Pernicious
Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap
First 60 primes	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
List of prime numbers