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

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

${\displaystyle b^{n}\equiv b{\pmod {n}}}$

для всех целых чисел ⁠ ⁠${\displaystyle б}$ . ^[1] Соотношение также может быть выражено ^[2] в виде:

${\displaystyle b^{n-1}\equiv 1{\pmod {n}}}$

для всех целых чисел , которые взаимно просты с ⁠ ⁠ . Их бесконечное количество. ^[3]${\displaystyle б}$${\displaystyle n}$

Они представляют собой сравнительно редкие случаи, когда строгое обращение Малой теоремы Ферма не выполняется. Этот факт исключает использование этой теоремы в качестве абсолютного теста простоты . ^[4]

Числа Кармайкла образуют подмножество K ₁ чисел Кнёделя .

Числа Кармайкла были названы в честь американского математика Роберта Кармайкла Николаасом Бигером в 1950 году. В 1948 году Ойстейн Оре назвал их числами со «свойством Ферма», или сокращенно «числами F ». ^[5]

Малая теорема Ферма гласит, что если — простое число , то для любого целого числа ⁠ ⁠ это число является целым числом, кратным ⁠ ⁠ . Числа Кармайкла — это составные числа, обладающие тем же свойством. Числа Кармайкла также называются псевдопростыми числами Ферма или абсолютными псевдопростыми числами Ферма . Число Кармайкла пройдет тест Ферма на простоту по каждому основанию, относительно простому числу, даже если оно на самом деле не является простым. Это делает тесты, основанные на Малой теореме Ферма, менее эффективными, чем сильные вероятные тесты на простоту, такие как тест простоты Бейли–ПСВ и тест простоты Миллера–Рабина .${\displaystyle p}$ ${\displaystyle б}$${\displaystyle b^{p}-b}$${\displaystyle p}$${\displaystyle б}$

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

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

${\displaystyle N=p\cdot (313(p-1)+1)\cdot (353(p-1)+1)}$

где

${\displaystyle p=}$ 2 9674495668 6855105501 5417464290 5332730771 9917998530 4335099507 5531276838 7531717701 9959423859 6428121188 0336647542 1834556249 3168782883

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

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

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

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

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

Первые семь чисел Кармайкла, от 561 до 8911, были найдены чешским математиком Вацлавом Шимеркой в ​​1885 году ^[11] (опередив, таким образом, не только Кармайкла, но и Корсельта, хотя Шимерка не нашел ничего похожего на критерий Корсельта). ^[12] Его работа, опубликованная в чешском научном журнале Časopis pro pěstování matematiky a fysiky , осталась незамеченной.

Корсельт был первым, кто наблюдал основные свойства чисел Кармайкла, но он не привел никаких примеров.

То, что 561 является числом Кармайкла, можно увидеть с помощью критерия Корсельта. Действительно, является бесквадратным и ⁠ ⁠ , и ⁠ ⁠ . Следующие шесть чисел Кармайкла (последовательность A002997 в OEIS ):${\displaystyle 561=3\cdot 11\cdot 17}$${\displaystyle 2\середина 560}$${\displaystyle 10\середина 560}$${\displaystyle 16\середина 560}$

${\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).}$

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

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

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

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

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

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

к
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 ): ^[8]${\displaystyle С(Х)}$${\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)}$

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

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

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

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

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

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

Относительно асимптотического распределения чисел Кармайкла было высказано несколько предположений. В 1956 году Эрдёш ^[17] предположил, что существуют числа Кармайкла для достаточно большого X. В 1981 году Померанс ^[20] усилил эвристические аргументы Эрдёша, предположив, что существуют по крайней мере${\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)}}$ .

Однако в пределах текущих вычислительных диапазонов (таких как подсчеты чисел Кармайкла, выполненные Пинчем ^[8] до 1021 ⁾ эти предположения пока не подтверждаются данными.

В 2021 году Дэниел Ларсен доказал аналог постулата Бертрана для чисел Кармайкла, впервые выдвинутых Элфордом, Грэнвиллом и Померансом в 1994 году. ^{[4] [21]} Используя методы, разработанные Итаном Чжаном и Джеймсом Мейнардом для установления результатов, касающихся малых промежутков между простыми числами , его работа дала гораздо более сильное утверждение, что для любого и достаточно большого в терминах , всегда будет по крайней мере ${\displaystyle \delta >0}$${\displaystyle x}$${\displaystyle \delta }$

${\displaystyle \exp {\left({\frac {\log {x}}{(\log \log {x})^{2+\delta }}}\right)}}$

Числа Кармайкла между и${\displaystyle x}$

${\displaystyle x+{\frac {x}{(\log {x})^{\frac {1}{2+\delta }}}}.}$

Понятие числа Кармайкла обобщается до идеала Кармайкла в любом числовом поле ⁠ ⁠${\displaystyle 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 m}$${\displaystyle 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 K}$${\displaystyle \mathbf {Q} }$${\displaystyle {\mathfrak {a}}}$${\displaystyle a}$${\displaystyle {\mathfrak {a}}=(a)}$${\displaystyle a}$

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

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

${\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 )

Числа квази-Кармайкла — это составные числа, свободные от квадратов , обладающие${\displaystyle n}$ свойством, что для любого простого множителя ⁠ ⁠${\displaystyle p}$ числа ⁠ ⁠${\displaystyle n}$ , ⁠ ⁠${\displaystyle p+b}$ делится ⁠ ⁠${\displaystyle n+b}$ положительно, причем ⁠ ⁠${\displaystyle b}$ является любым целым числом, кроме 0. Если ⁠ ⁠${\displaystyle b=-1}$ , то это числа Кармайкла, а если ⁠ ⁠${\displaystyle 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 в ОЭИС )

Число n - Кнёделя для данного положительного целого числа n - это составное число m со свойством, что каждое ⁠ ⁠ ${\displaystyle i<m}$ взаимно простое с m удовлетворяет ⁠ ⁠${\displaystyle i^{m-n}\equiv 1{\pmod {m}}}$ . Случай ⁠ ⁠${\displaystyle n=1}$ - числа Кармайкла.

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

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

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

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

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

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

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

• Кармайкл, РД (1910). «Заметка о новой функции теории чисел». Бюллетень Американского математического общества . 16 (5): 232–238. doi : 10.1090/s0002-9904-1910-01892-9 .
• Кармайкл, РД (1912). «О составных числах P , удовлетворяющих сравнению Ферма ». American Mathematical Monthly . 19 (2): 22–27. doi :10.2307/2972687. JSTOR  2972687.${\displaystyle a^{P-1}\equiv 1{\bmod {P}}}$
• Черник, Дж. (1939). «О простой теореме Ферма» (PDF) . Bull. Amer. Math. Soc . 45 (4): 269–274. doi : 10.1090/S0002-9904-1939-06953-X .
• Корсельт, Арканзас (1899 г.). «Китайская проблема». L'Intermediaire des Mathématiciens . 6 : 142–143.
• Löh, G.; Niebuhr, W. (1996). "Новый алгоритм построения больших чисел Кармайкла" (PDF) . Math. Comp . 65 (214): 823–836. Bibcode :1996MaCom..65..823L. doi : 10.1090/S0025-5718-96-00692-8 . Архивировано (PDF) из оригинала 2003-04-25.
• Рибенбойм, П. (1989). Книга рекордов простых чисел . Springer. ISBN 978-0-387-97042-4.
• Шимерка, В. (1885). «Збытки из арифметической послуупности» (О остатках арифметической прогрессии). Časopis Pro Pestování Matematicy and Fysiky . 14 (5): 221–225. дои : 10.21136/CPMF.1885.122245 .

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