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

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

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

для всех целых чисел $b$. Отношение может быть также выражено в виде:

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

для всех целых чисел $b$ которые относительно просты для $n$. Их бесконечно . число

Роберт Дэниел Кармайкл

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

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

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

Обзор

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

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

Арно дает 397-значное число Кармайкла $N$ это сильное псевдопростое число для всех простых оснований меньше 307:

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

где

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

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

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

Кореи

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

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

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

Открытие

Первые семь чисел Кармайкла, от 561 до 8911, были найдены чешским математиком Вацлавом Шимеркой в ​​1885 году. (таким образом, предшествуя не только Кармайклу, но и Корсельту, хотя Шимерка не нашел ничего похожего на критерий Корсельта). Однако его работа, опубликованная в чешском научном журнале Časopís pro přestování matematyky a fysyky , осталась незамеченной.

Вацлав Шимерка перечислил первые семь чисел Кармайкла.

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

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

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

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

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

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

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

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

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

Джек Черник в 1939 году доказал теорему, которую можно использовать для построения подмножества чисел Кармайкла. Номер $(6k+1)(12k+1)(18k+1)$является числом Кармайкла, если все его три фактора простые. Вопрос о том, дает ли эта формула бесконечное количество чисел Кармайкла, остается открытым (хотя это подразумевается гипотезой Диксона ).

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

Томас Райт доказал, что если $a$ и $m$являются относительно простыми, бесконечно много чисел Кармайкла тогда в арифметической прогрессии $a+k\cdot m$, где $k=1,2,\ldots$.

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

Свойства

Факторизации

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

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

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

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

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

Распространение

Позволять $C(X)$ обозначают количество чисел Кармайкла, меньших или равных $X$. Распределение чисел Кармайкла по степеням 10 (последовательность A055553 в OEIS ):

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
$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 году Кнедель доказал верхнюю оценку :

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

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

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

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

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

В другом направлении Алфорд , Гранвиль и Померанс оказались в 1994 году. что для достаточно большого X ,

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

В 2005 году эта граница была улучшена Харманом . к

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

который впоследствии улучшил показатель степени до $0.7039\cdot 0.4736=0.33336704>1/3$.

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

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

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

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

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

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

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

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

Обобщения

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

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

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

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

Число Лукаса–Кармайкла

Основная статья: число Лукаса – Кармайкла

Положительное составное целое число $n$ является числом Лукаса–Кармайкла тогда и только тогда, когда $n$ является свободным от квадратов и для всех простых делителей $p$ из $n$, правда, что $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 )

Число Квази-Кармайкла

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

Число пельменей

Основная статья: Число клецок

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

высшего

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

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

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

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

2

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

Свойства

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

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

Ссылки

• Кармайкл, Р.Д. (1910). «Заметка о новой функции теории чисел» . Бюллетень Американского математического общества . 16 (5): 232–238. дои : 10.1090/s0002-9904-1910-01892-9 .
• Кармайкл, РД (1912). «О составных числах P , удовлетворяющих сравнению Ферма $a^{P-1}\equiv 1{\bmod {P}}$". American Mathematical Monthly . 19 (2): 22–27. doi : 10.2307/2972687 . JSTOR   2972687 .
• Черник, Дж. (1939). «О простой теореме Ферма» (PDF) . Бык. амер. Математика. Соц . 45 (4): 269–274. дои : 10.1090/S0002-9904-1939-06953-X .
• Корсельт, А.Р. (1899). «Китайская проблема». Посредник математиков . 6 :142–143.
• Лё, Г.; Нибур, В. (1996). «Новый алгоритм построения больших чисел Кармайкла» (PDF) . Математика. Комп . 65 (214): 823–836. Бибкод : 1996MaCom..65..823L . дои : 10.1090/S0025-5718-96-00692-8 . Архивировано (PDF) из оригинала 25 апреля 2003 г.
• Рибенбойм, П. (1989). Книга рекордов простых чисел . Спрингер. ISBN  978-0-387-97042-4 .
• Шимерка, В. (1885). «Об остатках арифметической прогрессии» . Журнал по развитию математики и физики . 14 (5): 221–225. дои : 10.21136/CPMF.1885.122245 .

Внешние ссылки

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