Русская Википедия:Число Кармайкла
Число Кармайкла — составное число <math>n</math>, которое удовлетворяет сравнению <math>b^{n-1}\equiv 1\pmod{n}</math> для всех целых <math>b</math>, взаимно простых с <math>n</math>, другими словами — псевдопростое число по каждому основанию <math>b</math>, взаимно простому с <math>n</math>. Такие числа относительно редки, но их бесконечное число, наименьшее из них — 561; существование таких чисел делает недостаточным условие простоты малой теоремы Ферма, и не позволяет применять тест Ферма как универсальное средство проверки простоты.
Названы по имени американского математика Роберта Кармайкла.
Общие сведения
Малая теорема Ферма утверждает, что если <math>n</math> — простое число и <math>b</math> — целое число, не делящееся на <math>n</math>, то <math>b^{n-1}-1</math> делится на <math>n</math>, то есть <math>b^{n}\equiv b\pmod{n}</math>. Числа Кармайкла являются составными, при этом для них выполняется данное соотношение. Числа Кармайкла также называют абсолютно псевдопростыми числами Ферма, так как они являются псевдопростыми числами Ферма по каждому взаимно простому с ними основанию.
Существование чисел Кармайкла делает тест простоты Ферма менее эффективным для обнаружения простых чисел, по сравнению, например, с более строгим тестом Соловея — Штрассена, который распознаёт эти числа как составные. По мере возрастания числа Кармайкла становятся более редкими. Например, в промежутке от 1 до 1021 их содержится 20 138 200 (примерно одно на 50 триллионов чисел). Тем не менее, доказано, что существует бесконечно много чисел Кармайкла[1].
История
Первым, кто открыл числовые свойства, которые впоследствии стали характеристикой чисел Кармайкла, был Алвин Корсельт, доказавшим в 1899 году теорему о целых числах, эквивалентную условиям обращения малой теоремы Ферма, то есть для целых чисел <math>n</math>, для которых выполняется <math>b^{n}\equiv b\pmod{n} </math> при любых целых <math>b</math>: составное число <math> n </math> является числом Кармайкла тогда и только тогда, когда <math>n</math> свободно от квадратов и для каждого простого делителя <math>p</math> числа <math>n</math> число <math>p - 1</math> делит число <math>n-1</math>[2].
Корсельт оставил открытым вопрос поиска составных чисел, удовлетворяющих этому критерию. В 1910 году Кармайкл сформулировал критерий, по существу совпадающий с критерием Корсельта, и дал пример составного числа <math>n</math>, для которого он выполняется — <math>n = 561</math>. Это число раскладывается на простые множители как 561 = 3·11·17, и поэтому свободно от квадратов, в то время как <math>561-1=560</math> делится на 2, 10 и 16. После чего все контрпримеры получили наименование чисел Кармайкла.
В частности, из теоремы Корсельта следует, что все числа Кармайкла нечётны, так как любое чётное составное число, свободное от квадратов, имеет по крайней мере один нечётный простой делитель, и поэтому из делимости <math> p - 1 \mid n - 1</math> следует, что чётное делит нечётное, что невозможно.
В 1939 году Джон Черник доказал теорему, которая может быть использована для построения подмножества чисел Кармайкла: если <math>6m+1</math>, <math>12m+1</math>, <math>18m+1</math> — простые числа для одного натурального <math>m</math>, то их произведение <math>M_3 (m)=(6m+1)(12m+1)(18m+1)</math> является числом Кармайкла[2]. Это условие может быть удовлетворено, только если число <math>m</math> заканчивается цифрами 0, 1, 5 или 6 по основанию 10, то есть <math>m</math> сравнимо с 0 или 1 по модулю 5. Например, для <math>m=1</math> множители равны соответственно <math>7</math>, <math>13</math> и <math>19</math>, а их произведение даёт число Кармайкла 1729.
Способ нахождения чисел Кармайкла, предложенный Черником, может быть расширен на количество множителей <math>k\geqslant3</math>:
- <math>M_k(m) = (6m+1)(12m+1)\prod^{k-2}_{i=1}(9\cdot2^{i}m+1),\quad k\geqslant3</math>,
при условии, что все множители простые и <math>m</math> делится на <math>2^{k-4}</math>.
Гипотезу о бесконечности таких чисел высказал ещё Кармайкл в 1912 году, теорема Черника умозрительно повысила вероятность её выполнения; позднее Пал Эрдёш эвристически обосновал бесконечность чисел Кармайкла. Однако только в 1992 году[2] это утверждение было строго доказано Уильямом Алфордом, Эндрю Грэнвиллом и Карлом Померансом[1], точнее: доказано, что между 1 и достаточно большим <math>n</math> содержится <math>n^{2/7}</math> чисел Кармайкла.
В 1992 году Гюнтер Лё И Вольфганг Нибур предложили новый алгоритм для построения больших чисел Кармайкла: удалось найти число, получаемое перемножением Шаблон:Num простых чисел; это число содержит Шаблон:Num цифр[3].
Свойства
Теоремы Бигера и Дюпарка
В 1956 году Бигер доказал, что если для простых чисел <math>p</math>, <math>q</math> и <math>r</math> выполняется соотношение <math>p<q<r</math> и <math>pqr</math> — число Кармайкла, то <math>q<2p^2</math> и <math>r<p^3</math>. Таким образом, количество чисел Кармайкла, получаемых произведением трёх простых множителей, один из которых известен, конечно.
Дюпарк позже обобщил этот результат, чтобы показать, что если <math>n=mqr</math> — число Кармайкла, где <math>q</math> и <math>r</math> — простые, тогда <math>q<2m^2</math> и <math>r<m^3</math>. Следовательно, существует не более чем конечное количество чисел Кармайкла со всеми, кроме двух, определёнными множителями.
Случай <math>m</math> = 1 показывает, что любое кармайклово число содержит как минимум 3 простых множителя, к этому выводу впервые пришёл сам Кармайкл.
Разложения на простые множители
Разложения первых нескольких чисел Кармайкла на простые множители таковы:
- <math>\begin{align}
561 = 3 \cdot 11 \cdot 17 & \qquad (2 \mid 560; 10 \mid 560; 16 \mid 560),\\ 1105 = 5 \cdot 13 \cdot 17 & \qquad (4 \mid 1104; 12 \mid 1104; 16 \mid 1104),\\ 1729 = 7 \cdot 13 \cdot 19 & \qquad (6 \mid 1728; 12 \mid 1728; 18 \mid 1728),\\ 2465 = 5 \cdot 17 \cdot 29 & \qquad (4 \mid 2464; 16 \mid 2464; 28 \mid 2464),\\ 2821 = 7 \cdot 13 \cdot 31 & \qquad (6 \mid 2820; 12 \mid 2820; 30 \mid 2820),\\ 6601 = 7 \cdot 23 \cdot 41 & \qquad (6 \mid 6600; 22 \mid 6600; 40 \mid 6600),\\ 8911 = 7 \cdot 19 \cdot 67 & \qquad (6 \mid 8910; 18 \mid 8910; 66 \mid 8910). \end{align}</math> Кармайкловы числа имеют по меньшей мере три простых положительных множителя. Первые кармайкловы числа с <math>k = 3, 4, 5, \ldots</math> простыми множителями[4]:
| k | |
|---|---|
| 3 | <math>561 = 3 \cdot 11 \cdot 17</math> |
| 4 | <math>41041 = 7 \cdot 11 \cdot 13 \cdot 41</math> |
| 5 | <math>825265 = 5 \cdot 7 \cdot 17 \cdot 19 \cdot 73</math> |
| 6 | <math>321197185 = 5 \cdot 19 \cdot 23 \cdot 29 \cdot 37 \cdot 137</math> |
| 7 | <math>5394826801 = 7 \cdot 13 \cdot 17 \cdot 23 \cdot 31 \cdot 67 \cdot 73</math> |
| 8 | <math>232250619601 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 31 \cdot 37 \cdot 73 \cdot 163</math> |
| 9 | <math>9746347772161 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 31 \cdot 37 \cdot 41 \cdot 641</math> |
Первые кармайкловы числа с четырьмя простыми множителями[5]:
| i | |
|---|---|
| 1 | <math>41041 = 7 \cdot 11 \cdot 13 \cdot 41</math> |
| 2 | <math>62745 = 3 \cdot 5 \cdot 47 \cdot 89</math> |
| 3 | <math>63973 = 7 \cdot 13 \cdot 19 \cdot 37</math> |
| 4 | <math>75361 = 11 \cdot 13 \cdot 17 \cdot 31</math> |
| 5 | <math>101101 = 7 \cdot 11 \cdot 13 \cdot 101</math> |
| 6 | <math>126217 = 7 \cdot 13 \cdot 19 \cdot 73</math> |
| 7 | <math>172081 = 7 \cdot 13 \cdot 31 \cdot 61</math> |
| 8 | <math>188461 = 7 \cdot 13 \cdot 19 \cdot 109</math> |
| 9 | <math>278545 = 5 \cdot 17 \cdot 29 \cdot 113</math> |
| 10 | <math>340561 = 13 \cdot 17 \cdot 23 \cdot 67</math> |
Распределение
Следующая таблица показывает количество <math>C(X)</math> чисел Кармайкла меньше или равных числу <math>X</math>, которое задаётся как степень <math>n</math> десяти:[6]
| <math>n</math> | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| <math>C(10^n)</math> | 0 | 0 | 1 | 7 | 16 | 43 | 105 | 255 | 646 | 1547 | 3605 | 8241 | 19279 | 44706 | 105212 | 246683 |
В 1953 году Вальтер Кнёдель доказал, что:
- <math>C(X) < X \exp\left({-k_1 \left( \log X \log \log X\right)^\frac{1}{2}}\right)</math>
для некоторой константы <math>k_1</math>.
Пусть <math>C(X)</math> обозначает количество чисел Кармайкла, меньших <math>X</math>. Эрдёш доказал в 1956 году, что
- <math>C(X) < X \exp{\frac{-k_2 \log{X} \log{\log{\log{X}}}}{\log{\log{X}}}}</math>
для некоторой константы <math>k_2</math>. При этом также доказано[1], что существует бесконечно много чисел Кармайкла, то есть, <math>\lim_{X\to\infty} C(X) = \infty</math>.
В следующей таблице приведены приближённые минимальные значения константы k для значений X = 10n при разных n:
| <math>n</math> | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 | 21 |
|---|---|---|---|---|---|---|---|---|---|---|
| k | 2,19547 | 1,97946 | 1,90495 | 1,86870 | 1,86377 | 1,86293 | 1,86406 | 1,86522 | 1,86598 | 1,86619 |
Редкие свойства отдельных чисел
Второе кармайклово число (1105) может быть представлено как сумма двух квадратов большим количеством способов, чем любое меньшее число.
Третье кармайклово число (1729) является числом Рамануджана — Харди (наименьшее число, представимое в виде суммы двух кубов двумя способами).
Примечания
