Полный репенд прайм

В теории чисел , в полном расцвете reptend , полный расцвет рефрена , собственный простой ^{[1] : 166} или длинный простой в базовом б нечетного простого числа р такая , что фактор Ферма

${\ displaystyle q_ {p} (b) = {\ frac {b ^ {p-1} -1} {p}}}$

(где p не делит b ) дает циклическое число . Таким образом, цифровое расширение в базовом б повторяет цифры соответствующего циклического числа бесконечно, как и у с вращением цифры для любого а между 1 и р - 1. Циклическим число , соответствующее простым р будет обладать р - 1 цифр тогда и только тогда, когда p - простое число с полным повторением. То есть мультипликативный порядок ord _p b = p - 1, что эквивалентно тому, что b является a${\ displaystyle 1 / p}$${\ displaystyle a / p}$ первообразный корень по модулю p .

Термин «длинное простое число» использовали Джон Конвей и Ричард Гай в их Книге чисел . Как ни странно, в OEIS Слоана эти простые числа называются «циклическими числами».

База 10 [ править ]

База 10 может быть принята, если база не указана, и в этом случае расширение числа называется повторяющимся десятичным числом . В базе 10, если простое число с полным повторением заканчивается цифрой 1, то каждая цифра 0, 1, ..., 9 появляется в повторении такое же количество раз, что и каждая другая цифра. ^{[1] : 166} (Для таких простых чисел с основанием 10 см. OEIS :  A073761 . Фактически, в базе b , если полное повторение простого числа заканчивается цифрой 1, то каждая цифра 0, 1, ..., b −1 появляется в повторении такое же количество раз, как и каждая другая цифра, но такого простого числа не существует, когда b = 12, так как каждое полное повторение простого числа в базе 12оканчивается цифрой 5 или 7 в том же основании. Как правило, нет такой простой , не существует , когда б является конгруэнтны 0 или 1 по модулю 4.

Значения p меньше 1000, для которых эта формула дает циклические числа в десятичной системе, следующие:

7 , 17 , 19 , 23 , 29 , 47 , 59 , 61 , 97 , 109 , 113 , 131 , 149 , 167 , 179 , 181 , 193 , 223 , 229 , 233 , 257 , 263 , 269 , 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577, 593, 619, 647, 659, 701, 709, 727, 743, 811 , 821, 823, 857, 863, 887, 937, 941, 953, 971, 977, 983, ... (последовательность A001913 в OEIS )

Например, случай b = 10, p = 7 дает циклическое число 142857 ; таким образом 7 - простое число с полным повторением. Кроме того, 1, деленная на 7, записанная в базе 10, дает 0,142857 142857 142857 142857 ...

Не все значения p дадут циклическое число с использованием этой формулы; например, p = 13 дает 076923 076923. Эти неудачные случаи всегда будут содержать повторение цифр (возможно, нескольких) в течение p - 1 цифр.

Известный образец этой последовательности исходит из теории алгебраических чисел , в частности, эта последовательность представляет собой набор простых чисел p, таких, что 10 является примитивным корнем по модулю p . Гипотеза Артина о первообразных корнях состоит в том, что эта последовательность содержит 37,395 ..% простых чисел.

Паттерны появления простых чисел с полным повторением [ править ]

Расширенная модульная арифметика может показать, что любое простое число из следующих форм:

Никогда не может быть полным повторением простого числа с основанием 10. Первые простые числа этих форм с их периодами:

Однако исследования показывают, что две трети простых чисел вида 40 k  +  n , где n  ∈ {7, 11, 17, 19, 21, 23, 29, 33}, являются простыми числами с полным повторением. Для некоторых последовательностей преобладание простых чисел с полным повторением намного больше. Например, 285 из 295 простых чисел формы 120 k  + 23 ниже 100000 являются простыми числами с полным повторением, причем 20903 является первым, которое не является полным повторением.

Бинарные простые числа с полным повторением [ править ]

В базе 2 простые числа с полным повторением: (менее 1000)

3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, 613, 619, 653, 659, 661, 677, 701, 709, 757, 773, 787, 797, 821, 827, 829, 853, 859, 877, 883, 907, 941, 947, ... (последовательность A001122 в OEIS )

Для этих простых чисел 2 является первообразным корнем по модулю p , поэтому 2 ⁿ по модулю p может быть любым натуральным числом от 1 до p - 1.

${\ Displaystyle а (я) = 2 ^ {я} ~ {\ bmod {p}} ~ {\ bmod {2}}}$

Эти последовательности периода p - 1 имеют функцию автокорреляции, которая имеет отрицательный пик -1 для сдвига . Случайность этих последовательностей была проверена жесткими тестами . ^[2]${\ Displaystyle (п-1) / 2}$

Все они имеют форму 8 k + 3 или 8 k + 5, потому что, если p = 8 k + 1 или 8 k + 7, то 2 является квадратичным вычетом по модулю p , поэтому p делится , а период по основанию 2 должны делиться и не могут быть p - 1, поэтому они не являются полностью повторяющимися простыми числами с основанием 2.${\ Displaystyle 2 ^ {(п-1) / 2} -1}$${\ displaystyle 1 / p}$${\ Displaystyle (п-1) / 2}$

Кроме того, все безопасные простые числа, конгруэнтные 3 (модификация 8), являются простыми числами с полным повторением в основании 2. Например, 3, 11, 59, 83, 107, 179, 227, 347, 467, 563, 587, 1019, 1187, 1283 , 1307, 1523, 1619, 1907 и др. (Менее 2000)

Двоичные последовательности простых чисел с полным повторением (также называемые десятичными последовательностями максимальной длины) нашли применение в криптографии и кодировании с исправлением ошибок. ^[3] В этих приложениях обычно используются повторяющиеся десятичные дроби с основанием 2, что приводит к двоичным последовательностям. Максимальная длина двоичной последовательности для (когда 2 является примитивным корнем из p ) задается следующим образом: ^[4]${\ displaystyle 1 / p}$

Ниже приводится список периодов (в двоичном формате) простых чисел, конгруэнтных 1 или 7 (модификация 8): (менее 1000)

Ни один из них не является бинарным простым числом с полным повторением.

Двоичный период n- го простого числа равен

2, 4, 3, 10, 12, 8, 18, 11, 28, 5, 36, 20, 14, 23, 52, 58, 60, 66, 35, 9, 39, 82, 11, 48, 100, 51, 106, 36, 28, 7, 130, 68, 138, 148, 15, 52, 162, 83, 172, 178, 180, 95, 96, 196, 99, 210, 37, 226, 76, 29, 119, 24, 50, 16, 131, 268, 135, 92, 70, 94, 292, 102, 155, 156, 316, 30, 21, 346, 348, 88, 179, 183, 372, 378, 191, 388, 44, ... (эта последовательность начинается с n = 2 или простого числа = 3) (последовательность A014664 в OEIS )

Уровень двоичного периода n- го простого числа равен

1, 1, 2, 1, 1, 2, 1, 2, 1, 6, 1, 2, 3, 2, 1, 1, 1, 1, 2, 8, 2, 1, 8, 2, 1, 2, 1, 3, 4, 18, 1, 2, 1, 1, 10, 3, 1, 2, 1, 1, 1, 2, 2, 1, 2, 1, 6, 1, 3, 8, 2, 10, 5, 16, 2, 1, 2, 3, 4, 3, 1, 3, 2, 2, 1, 11, 16, 1, 1, 4, 2, 2, 1, 1, 2, 1, 9, 2, 2, 1, 1, 10, 6, 6, 1, 2, 6, 1, 2, 1, 2, 2, 1, 3, 2, 1, 2, 1, 1, .. . (последовательность A001917 в OEIS )

Однако исследования показывают, что три четверти простых чисел формы 8 k + n , где n ∈ {3, 5} - простые числа с полным повторением в основании 2 (например, есть 87 простых чисел меньше 1000, конгруэнтных 3 или 5 (mod 8), из них 67 полноценных по базе 2, итого 77%). Для некоторых последовательностей преобладание простых чисел с полным повторением намного больше. Например, 1078 из 1206 простых чисел формы 24 k +5 ниже 100000 являются простыми числами с полным повторением по основанию 2, причем 1013 является первым, которое не полностью повторяется по основанию 2.

простое повторение n -го уровня [ править ]

П -го уровня reptend главным является простым р , имеющим п разных циклов в разложении ( к представляет собой целое число, 1 ≤ K ≤ р -1). В базе 10 наименьшее число повторений n-го уровня равно${\ displaystyle {\ frac {k} {p}}}$

7, 3, 103, 53, 11, 79, 211, 41, 73, 281, 353, 37, 2393, 449, 3061, 1889, 137, 2467, 16189, 641, 3109, 4973, 11087, 1321, 101, 7151, 7669, 757, 38629, 1231, 49663, 12289, 859, 239, 27581, 9613, 18131, 13757, 33931, 9161, 118901, 6763, 18233, 1409, 88741, 4003, 5171, 19489, 86143, 23201, ... (последовательность A054471 в OEIS )

В базе 2 наименьшее число повторений n-го уровня равно

3, 7, 43, 113, 251, 31, 1163, 73, 397, 151, 331, 1753, 4421, 631, 3061, 257, 1429, 127, 6043, 3121, 29611, 1321, 18539, 601, 15451, 14327, 2971, 2857, 72269, 3391, 683, 2593, 17029, 2687, 42701, 11161, 13099, 1103, 71293, 13121, 17467, 2143, 83077, 25609, 5581, 5153, 26227, 2113, 51941, 2351, ... (последовательность A101208 в OEIS )

Простые числа с полным повторением в различных базах [ править ]

Артин также предположил:

• Существует бесконечно много простых чисел с полным повторением во всех основаниях, кроме квадратов .
• Полностью повторяющиеся простые числа во всех основаниях, кроме совершенных степеней и чисел, бесквадратная часть которых конгруэнтна 1 по модулю 4, составляют 37,395 ...% всех простых чисел. (См. OEIS :  A085397 )

Наименьшие простые числа с полным повторением в базе n :

2, 3, 2, 0, 2, 11, 2, 3, 2, 7, 2, 5, 2, 3, 2, 0, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 11, 2, 3, 2, 19, 2, 0, 2, 3, 2, 7, 2, 5, 2, 3, 2, 11, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 19, 2, 3, 2, 0, 2, 7, 2, 3, 2, 19, 2, 5, 2, 3, 2, 13, 2, 5, 2, 3, 2, 5, 2, 11, 2, 3, 2, 5, 2, 11, 2, 3, 2, 7, 2, 7, 2, 3, 2, 0, ... (последовательность A056619 в OEIS )

См. Также [ править ]

• Повторяющаяся десятичная дробь

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

• Вайсштейн, Эрик В. «Константа Артина» . MathWorld .
• Вайсштейн, Эрик В. «Полный Reptend Prime» . MathWorld .
• Conway, JH и Гай, Р.К. . Книга чисел. Нью-Йорк: Springer-Verlag, 1996.
• Фрэнсис, Ричард Л .; «Математические стога сена: новый взгляд на числа повторного объединения»; в журнале College Mathematics Journal , Vol. 19, № 3. (май 1988 г.), стр. 240–246.