Число Кармайкла

В теории чисел число Кармайкла - это составное число, удовлетворяющее модульному арифметическому соотношению конгруэнтности:${\ displaystyle n}$

${\ Displaystyle Ь ^ {п-1} \ эквив 1 {\ pmod {п}}}$

для всех целых чисел, которые взаимно просты с . ^[1] Они названы в честь Роберта Кармайкла . Числа Carmichael являются подмножество К ₁ из чисел Knodel .${\ displaystyle b}$${\ displaystyle n}$

Аналогично, число Кармайкла - это составное число, для которого${\ displaystyle n}$

${\ Displaystyle б ^ {п} \ эквив б {\ pmod {п}}}$

для всех целых чисел . ^[2]${\ displaystyle b}$

Обзор [ править ]

Маленькая теорема Ферма утверждает, что если p - простое число , то для любого целого числа b число b ^p  -  b является целым кратным p . Числа Кармайкла - это составные числа, обладающие этим свойством. Числа Кармайкла также называют псевдопростыми числами Ферма или абсолютными псевдопростыми числами Ферма . Число Кармайкла пройдет проверку на простоту Ферма для каждого основания b, относительно простого числа, даже если оно на самом деле не является простым. Это делает тесты, основанные на Маленькой теореме Ферма, менее эффективными, чем сильное вероятное простое число.такие тесты, как критерий простоты Бэйли – PSW и критерий простоты Миллера – Рабина .

Однако никакое число Кармайкла не является ни псевдопервичным числом Эйлера – Якоби, ни сильным псевдопервичным основанием по отношению к любому основанию, относительно простому с ним ^[3], поэтому теоретически либо критерий Эйлера, либо строгий вероятностный критерий простого числа могут доказать, что число Кармайкла на самом деле является , композит.

Арно ^[4] дает 397-значное число Кармайкла, которое является сильным псевдопростом для всех простых оснований меньше 307:${\ displaystyle N}$

${\ Displaystyle N = п \ CDOT (313 (р-1) +1) \ CDOT (353 (р-1) +1)}$

где

${\ displaystyle p =}$29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883

является 131-значным простым числом. является наименьшим простым делителем числа Кармайкла, поэтому это число Кармайкла также является (не обязательно сильным) псевдопростом для всех оснований, меньших чем .${\ displaystyle p}$${\ displaystyle N}$${\ displaystyle p}$

По мере того, как числа становятся больше, числа Кармайкла становятся все более редкими. Например, есть 20 138 200 чисел Кармайкла от 1 до 10 ²¹ (примерно одно из 50 триллионов (5 · 10 ¹³ ) чисел). ^[5]

Критерий Корсельта [ править ]

Альтернативное и эквивалентное определение чисел Кармайкла дается критерием Корсельта .

Теорема ( A. Korselt 1899): Положительное составное целое число является числом Кармайкла тогда и только тогда, когда оно бесквадратное , и для всех простых делителей числа верно, что .${\ displaystyle n}$${\ displaystyle n}$ ${\ displaystyle p}$${\ displaystyle n}$${\ displaystyle p-1 \ mid n-1}$

Из этой теоремы следует, что все числа Кармайкла нечетные , поскольку любое четное составное число, свободное от квадратов (и, следовательно, имеющее только один простой делитель из двух), будет иметь по крайней мере один нечетный простой делитель , и, таким образом, приведет к четному делению числа. странно, противоречие. (Нечетность чисел Кармайкла также следует из того факта, что это свидетельство Ферма для любого четного составного числа.) Из критерия также следует, что числа Кармайкла циклические . ^{[6] [7]} Кроме того, отсюда следует, что не существует чисел Кармайкла с ровно двумя простыми делителями.${\ displaystyle p-1 \ mid n-1}$${\ displaystyle -1}$

Открытие [ править ]

Корсельт был первым, кто обнаружил основные свойства чисел Кармайкла, но не привел никаких примеров. В 1910 году Кармайкл ^[8] нашел первое и наименьшее такое число, 561, что объясняет название «число Кармайкла».

То, что 561 - это число Кармайкла, можно увидеть с помощью критерия Корселта. Действительно, является бесквадратным и , и .${\ Displaystyle 561 = 3 \ cdot 11 \ cdot 17}$${\ displaystyle 2 \ mid 560}$${\ displaystyle 10 \ mid 560}$${\ displaystyle 16 \ mid 560}$

Следующие шесть чисел Кармайкла (последовательность A002997 в OEIS ):

${\ displaystyle 1105 = 5 \ cdot 13 \ cdot 17 \ qquad (4 \ mid 1104; \ quad 12 \ mid 1104; \ quad 16 \ mid 1104)}$

${\ displaystyle 1729 = 7 \ cdot 13 \ cdot 19 \ qquad (6 \ mid 1728; \ quad 12 \ mid 1728; \ quad 18 \ mid 1728)}$

${\displaystyle 2465=5\cdot 17\cdot 29\qquad (4\mid 2464;\quad 16\mid 2464;\quad 28\mid 2464)}$

${\displaystyle 2821=7\cdot 13\cdot 31\qquad (6\mid 2820;\quad 12\mid 2820;\quad 30\mid 2820)}$

${\displaystyle 6601=7\cdot 23\cdot 41\qquad (6\mid 6600;\quad 22\mid 6600;\quad 40\mid 6600)}$

${\displaystyle 8911=7\cdot 19\cdot 67\qquad (6\mid 8910;\quad 18\mid 8910;\quad 66\mid 8910).}$

Все эти первые семь чисел Кармайкла от 561 до 8911 были найдены чешским математиком Вацлавом Шимеркой  [ de ; cs ] в 1885 году ^[9] (таким образом, предшествует не только Кармайклу, но и Корсельту, хотя Шимерка не нашла ничего похожего на критерий Корсельта). ^[10] Его работа, однако, осталась незамеченной.

Дж. Черник ^[11] в 1939 году доказал теорему, которую можно использовать для построения подмножества чисел Кармайкла. Число является числом Кармайкла, если все три его множителя простые. Дает ли эта формула бесконечное количество чисел Кармайкла - вопрос открытый (хотя это подразумевается гипотезой Диксона ).${\displaystyle (6k+1)(12k+1)(18k+1)}$

Пол Эрдеш эвристически утверждал, что чисел Кармайкла должно быть бесконечно много. В 1994 году WR (Красный) Алфорд , Эндрю Грэнвилл и Карл Померанс использовали оценку константы Олсона, чтобы показать, что действительно существует бесконечно много чисел Кармайкла. В частности, они показали, что для достаточно больших есть, по крайней мере, числа Кармайкла от 1 до . ^[12]${\displaystyle n}$${\displaystyle n^{2/7}}$${\displaystyle n}$

Томас Райт доказал, что если и являются взаимно простыми числами, то в арифметической прогрессии существует бесконечно много чисел Кармайкла , где . ^[13]${\displaystyle a}$${\displaystyle m}$${\displaystyle a+k\cdot m}$${\displaystyle k=1,2,\ldots }$

Лё и Нибур в 1992 году нашли несколько очень больших чисел Кармайкла, в том числе одно с 1 101 518 множителями и более 16 миллионами цифр. Это было улучшено до 10 333 229 505 простых множителей и 295 486 761 787 цифр ^[14], так что наибольшее известное число Кармайкла намного больше наибольшего известного простого числа .

Свойства [ править ]

Факторизации [ править ]

У чисел Кармайкла есть как минимум три положительных простых множителя. Первые числа Кармайкла с простыми множителями (последовательность A006931 в OEIS ):${\displaystyle k=3,4,5,\ldots }$

k
3	${\displaystyle 561=3\cdot 11\cdot 17\,}$
4	${\displaystyle 41041=7\cdot 11\cdot 13\cdot 41\,}$
5	${\displaystyle 825265=5\cdot 7\cdot 17\cdot 19\cdot 73\,}$
6	${\displaystyle 321197185=5\cdot 19\cdot 23\cdot 29\cdot 37\cdot 137\,}$
7	${\displaystyle 5394826801=7\cdot 13\cdot 17\cdot 23\cdot 31\cdot 67\cdot 73\,}$
8	${\displaystyle 232250619601=7\cdot 11\cdot 13\cdot 17\cdot 31\cdot 37\cdot 73\cdot 163\,}$
9	${\displaystyle 9746347772161=7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 31\cdot 37\cdot 41\cdot 641\,}$

Первые числа Кармайкла с 4 простыми множителями (последовательность A074379 в OEIS ):

я
1	${\displaystyle 41041=7\cdot 11\cdot 13\cdot 41\,}$
2	${\displaystyle 62745=3\cdot 5\cdot 47\cdot 89\,}$
3	${\displaystyle 63973=7\cdot 13\cdot 19\cdot 37\,}$
4	${\displaystyle 75361=11\cdot 13\cdot 17\cdot 31\,}$
5	${\displaystyle 101101=7\cdot 11\cdot 13\cdot 101\,}$
6	${\displaystyle 126217=7\cdot 13\cdot 19\cdot 73\,}$
7	${\displaystyle 172081=7\cdot 13\cdot 31\cdot 61\,}$
8	${\displaystyle 188461=7\cdot 13\cdot 19\cdot 109\,}$
9	${\displaystyle 278545=5\cdot 17\cdot 29\cdot 113\,}$
10	${\displaystyle 340561=13\cdot 17\cdot 23\cdot 67\,}$

Второе число Кармайкла (1105) может быть выражено как сумма двух квадратов большим количеством способов, чем любое меньшее число. Третье число Кармайкла (1729) - это число Харди-Рамануджана : наименьшее число, которое может быть выражено как сумма двух кубиков (положительных чисел) двумя разными способами.

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

Позвольте обозначить количество чисел Кармайкла, меньшее или равное . Распределение чисел Кармайкла по степеням 10 (последовательность A055553 в OEIS ): ^[5]${\displaystyle C(X)}$${\displaystyle X}$

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21 год
${\displaystyle C(10^{n})}$	0	0	1	7	16	43 год	105	255	646	1547	3605	8241	19279	44706	105212	246683	585355	1401644	3381806	8220777	20138200

В 1953 году Кнёдель доказал верхнюю оценку :

${\displaystyle C(X)<X\exp \left({-k_{1}\left(\log X\log \log X\right)^{\frac {1}{2}}}\right)}$

для некоторой константы .${\displaystyle k_{1}}$

В 1956 году Эрдеш улучшил оценку

${\displaystyle C(X)<X\exp \left({\frac {-k_{2}\log X\log \log \log X}{\log \log X}}\right)}$

для некоторой константы . ^[15] Далее он привел эвристический аргумент, предполагающий, что эта верхняя граница должна быть близкой к истинной скорости роста .${\displaystyle k_{2}}$${\displaystyle C(X)}$

В другом направлении, Олфорд , Гранвилль и Померанс доказано в 1994 году ^[12] , что при достаточно большом X ,

${\displaystyle C(X)>X^{\frac {2}{7}}.}$

В 2005 г. эта оценка была дополнительно улучшена Харманом ^[16] до

${\displaystyle C(X)>X^{0.332}}$

который впоследствии улучшил показатель до .^[17]${\displaystyle 0.7039\cdot 0.4736=0.33336704>1/3}$

Относительно асимптотического распределения чисел Кармайкла было высказано несколько предположений. В 1956 г. Эрдеш ^[15] предположил, что числа Кармайкла для X достаточно велики. В 1981 г. Померанс ^[18] уточнил эвристические аргументы Эрдеша, чтобы предположить, что существует по крайней мере${\displaystyle X^{1-o(1)}}$

${\displaystyle X\cdot L(X)^{-1+o(1)}}$

Кармайкл числа до , где .${\displaystyle X}$${\displaystyle L(x)=\exp {\left({\frac {\log x\log \log \log x}{\log \log x}}\right)}}$

Однако в рамках текущих расчетных диапазонов (таких как подсчет чисел Кармайкла, выполненный Пинчем ^[5] до 10 ²¹ ), эти предположения еще не подтверждаются данными.

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

Понятие числа Carmichael обобщающего к идеалу Carmichael в любом числовом поле K . Для любого ненулевого простого идеала in мы имеем for all in , где - норма идеала . (Это обобщает маленькую теорему Ферма о том, что для всех целых чисел m, когда p простое.) Назовите ненулевым идеалом в Кармайкле, если он не является простым идеалом, и для всех , где - норма идеала . Когда K является , идеал является главным , и если мы позволим${\displaystyle {\mathfrak {p}}}$${\displaystyle {\mathcal {O}}_{K}}$${\displaystyle \alpha ^{{\rm {N}}({\mathfrak {p}})}\equiv \alpha {\bmod {\mathfrak {p}}}}$${\displaystyle \alpha }$${\displaystyle {\mathcal {O}}_{K}}$${\displaystyle {\rm {N}}({\mathfrak {p}})}$ ${\displaystyle {\mathfrak {p}}}$${\displaystyle m^{p}\equiv m{\bmod {p}}}$${\displaystyle {\mathfrak {a}}}$${\displaystyle {\mathcal {O}}_{K}}$${\displaystyle \alpha ^{{\rm {N}}({\mathfrak {a}})}\equiv \alpha {\bmod {\mathfrak {a}}}}$${\displaystyle \alpha \in {\mathcal {O}}_{K}}$${\displaystyle {\rm {N}}({\mathfrak {a}})}$${\displaystyle {\mathfrak {a}}}$${\displaystyle \mathbf {Q} }$${\displaystyle {\mathfrak {a}}}$быть его положительным генератором, то идеал - это Кармайкл, когда a - число Кармайкла в обычном смысле.${\displaystyle {\mathfrak {a}}=(a)}$

Когда K больше, чем рациональные числа, легко записать идеалы Кармайкла в : для любого простого числа p, которое полностью разделяется в K , главный идеал является идеалом Кармайкла. Поскольку бесконечно много простых чисел полностью распадаются в любом числовом поле, в нем бесконечно много идеалов Кармайкла . Например, если p - любое простое число, равное 1 по модулю 4, идеал ( p ) в гауссовских целых числах Z [ i ] является идеалом Кармайкла.${\displaystyle {\mathcal {O}}_{K}}$${\displaystyle p{\mathcal {O}}_{K}}$${\displaystyle {\mathcal {O}}_{K}}$   

И простые числа, и числа Кармайкла удовлетворяют следующему равенству:

${\displaystyle \gcd \left(\sum _{x=1}^{n-1}x^{n-1},n\right)=1.}$

Число Лукаса – Кармайкла [ править ]

Положительное составное целое число является числом Лукаса – Кармайкла тогда и только тогда, когда оно не содержит квадратов , и для всех простых делителей числа верно, что . Первые числа Лукаса – Кармайкла:${\displaystyle n}$${\displaystyle n}$ ${\displaystyle p}$${\displaystyle n}$${\displaystyle p+1\mid n+1}$

399, 935, 2015, 2915, 4991, 5719, 7055, 8855, 12719, 18095, 20705, 20999, 22847, 29315, 31535, 46079, 51359, 60059, 63503, 67199, 73535, 76751, 80189, 81719, 88559, 90287, ... (последовательность A006972 в OEIS )

Квази – число Кармайкла [ править ]

Номера Квази-Carmichael являются бесквадратно составными числами п со свойством , что для каждого простого множителя р от п , р  +  б делит п  +  Ь положительно б быть любым целым числом , кроме 0. Если б = -1, это число Carmichael, и если b = 1, это числа Люка – Кармайкла. Первые числа Квази – Кармайкла:

35, 77, 143, 165, 187, 209, 221, 231, 247, 273, 299, 323, 357, 391, 399, 437, 493, 527, 561, 589, 598, 713, 715, 899, 935, 943, 989, 1015, 1073, 1105, 1147, 1189, 1247, 1271, 1295, 1333, 1517, 1537, 1547, 1591, 1595, 1705, 1729, ... (последовательность A257750 в OEIS )

Номер Knödel [ править ]

П - Knödel номер для заданного положительного целого числа п является составным числом м со свойством , что каждый я  <  т взаимно просты с т удовлетворяет . П = 1 случай являются числами Carmichael.${\displaystyle i^{m-n}\equiv 1{\pmod {m}}}$

Числа Кармайкла высшего порядка [ править ]

Числа Кармайкла можно обобщить, используя понятия абстрактной алгебры .

Приведенное выше определение утверждает, что составное целое число n является Кармайклом именно тогда, когда функция p _n, повышающая n- ю степень, из кольца Z _n целых чисел по модулю n сама себе является функцией тождества. Тождество является единственным эндоморфизмом Z _n - алгебры на Z _n, поэтому мы можем переформулировать определение, задавая вопрос о том, что p _n является эндоморфизмом алгебры Z _n . Как и выше, p _n удовлетворяет тому же свойству, когда n простое.

П - й мощности по повышению функции р _п также определяется на любом Z _п - алгебры A . Теорема утверждает, что n простое тогда и только тогда, когда все такие функции p _n являются эндоморфизмами алгебры.

Между этими двумя условиями находится определение числа Кармайкла порядка m для любого положительного целого числа m как любого составного числа n такого, что p _n является эндоморфизмом на каждой Z _n -алгебре, которая может быть сгенерирована как Z _n - модуль из m элементов. . Числа Кармайкла порядка 1 - это просто обычные числа Кармайкла.

Номер Кармайкла порядка 2 [ править ]

Согласно Хоу, 17 · 31 · 41 · 43 · 89 · 97 · 167 · 331 - это число Кармайкла порядка 2. Этот продукт равен 443,372,888,629,441. ^[19]

Свойства [ править ]

Критерий Корселта можно обобщить на числа Кармайкла более высокого порядка, как показано Хоу.

Эвристический аргумент, приведенный в той же статье, по-видимому, предполагает, что существует бесконечно много чисел Кармайкла порядка m для любого m . Однако не известно ни одного числа Кармайкла порядка 3 или выше.

Заметки [ править ]

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

• Кармайкл, Р. Д. (1910). «Заметка о новой функции теории чисел» . Бюллетень Американского математического общества . 16 (5): 232–238. DOI : 10.1090 / s0002-9904-1910-01892-9 .
• Кармайкл, RD (1912). «О составных числах P, удовлетворяющих сравнению Ферма ». Американский математический ежемесячник . 19 (2): 22–27. DOI : 10.2307 / 2972687 . JSTOR 2972687 .${\displaystyle a^{P-1}\equiv 1{\bmod {P}}}$ 
• Черник, Дж. (1939). «О простой теореме Ферма» (PDF) . Бык. Амер. Математика. Soc . 45 (4): 269–274. DOI : 10.1090 / S0002-9904-1939-06953-X .
• Корсельт, АР (1899). "Problème chinois". L'Intermédiaire des Mathématiciens . 6 : 142–143.
• Löh, G .; Нибур, В. (1996). «Новый алгоритм построения больших чисел Кармайкла» (PDF) . Математика. Комп . 65 (214): 823–836. Bibcode : 1996MaCom..65..823L . DOI : 10.1090 / S0025-5718-96-00692-8 .
• Рибенбойм, П. (1989). Книга рекордов простых чисел . Springer. ISBN 978-0-387-97042-4.
• Шимерка, В. (1885). "Zbytky z arithmetické posloupnosti (Об остатках арифметической прогрессии)" . Časopis Pro Pěstování Matematiky a Fysiky . 14 (5): 221–225.

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

• «Число Кармайкла» , Энциклопедия математики , EMS Press , 2001 [1994]
• Энциклопедия математики
• Таблица чисел Кармайкла
• Таблицы чисел Кармайкла с множеством простых множителей
• Таблицы чисел Кармайкла ниже 10 18 {\displaystyle 10^{18}}
• «Тусклость 1729 года» . MathPages.com .
• Вайсштейн, Эрик В. «Число Кармайкла» . MathWorld .
• Окончательные ответы Модульная арифметика