Число Кармайкла
Число Кармайкла — составное число [math]\displaystyle{ n }[/math], которое удовлетворяет сравнению [math]\displaystyle{ b^{n-1}\equiv 1\pmod{n} }[/math] для всех целых [math]\displaystyle{ b }[/math], взаимно простых с [math]\displaystyle{ n }[/math], другими словами — псевдопростое число по каждому основанию [math]\displaystyle{ b }[/math], взаимно простому с [math]\displaystyle{ n }[/math]. Такие числа относительно редки, но их бесконечное число, наименьшее из них — 561; существование таких чисел делает недостаточным условие простоты малой теоремы Ферма, и не позволяет применять тест Ферма как универсальное средство проверки простоты.
Названы по имени американского математика Роберта Кармайкла.
Общие сведения
Малая теорема Ферма утверждает, что если [math]\displaystyle{ n }[/math] — простое число и [math]\displaystyle{ b }[/math] — целое число, не делящееся на [math]\displaystyle{ n }[/math], то [math]\displaystyle{ b^{n-1}-1 }[/math] делится на [math]\displaystyle{ n }[/math], то есть [math]\displaystyle{ b^{n}\equiv b\pmod{n} }[/math]. Числа Кармайкла являются составными, при этом для них выполняется данное соотношение. Числа Кармайкла также называют абсолютно псевдопростыми числами Ферма, так как они являются псевдопростыми числами Ферма по каждому взаимно простому с ними основанию.
Существование чисел Кармайкла делает тест простоты Ферма менее эффективным для обнаружения простых чисел, по сравнению, например, с более строгим тестом Соловея — Штрассена, который распознаёт эти числа как составные. По мере возрастания числа Кармайкла становятся более редкими. Например, в промежутке от 1 до 1021 их содержится 20 138 200 (примерно одно на 50 триллионов чисел). Тем не менее, доказано, что существует бесконечно много чисел Кармайкла[1].
История
Первым, кто открыл числовые свойства, которые впоследствии стали характеристикой чисел Кармайкла, был Алвин Корсельт, доказавшим в 1899 году теорему о целых числах, эквивалентную условиям обращения малой теоремы Ферма, то есть для целых чисел [math]\displaystyle{ n }[/math], для которых выполняется [math]\displaystyle{ b^{n}\equiv b\pmod{n} }[/math] при любых целых [math]\displaystyle{ b }[/math]: составное число [math]\displaystyle{ n }[/math] является числом Кармайкла тогда и только тогда, когда [math]\displaystyle{ n }[/math] свободно от квадратов и для каждого простого делителя [math]\displaystyle{ p }[/math] числа [math]\displaystyle{ n }[/math] число [math]\displaystyle{ p - 1 }[/math] делит число [math]\displaystyle{ n-1 }[/math][2].
Пусть, что [math]\displaystyle{ b^{n}\equiv b\pmod{n} }[/math] для всех целых [math]\displaystyle{ b }[/math]. Сначала докажем, что число [math]\displaystyle{ n }[/math] должно быть свободно от квадратов. Предположим, что это не так и [math]\displaystyle{ k^2 \mid n }[/math] ([math]\displaystyle{ k^2 }[/math] делит [math]\displaystyle{ n }[/math]) для некоторого целого [math]\displaystyle{ k\gt 1 }[/math]. Пусть [math]\displaystyle{ b = k }[/math], тогда [math]\displaystyle{ k^{n}\equiv k\pmod{n} }[/math]. Так как [math]\displaystyle{ k^2 \mid n }[/math], то это соотношение верно по модулю [math]\displaystyle{ k^2 }[/math], то есть [math]\displaystyle{ k^{n}\equiv k\pmod{k^2} }[/math], что противоречит выражению [math]\displaystyle{ k^{n}\equiv 0\pmod{k^2} }[/math]. Таким образом, число [math]\displaystyle{ n }[/math] свободно от квадратов. Пусть теперь [math]\displaystyle{ p }[/math] – простой делитель числа [math]\displaystyle{ n }[/math]. Известно, что мультипликативная группа [math]\displaystyle{ (\mathbb{Z}/p\mathbb{Z})^* }[/math] кольца вычетов по модулю [math]\displaystyle{ p }[/math], где [math]\displaystyle{ p }[/math] – простое, является циклической группой порядка [math]\displaystyle{ p - 1 }[/math]. Пусть [math]\displaystyle{ b }[/math] – целое число, такое, что [math]\displaystyle{ b\pmod{p} }[/math] – генератор группы [math]\displaystyle{ (\mathbb{Z}/p\mathbb{Z})^* }[/math]. Так как [math]\displaystyle{ b^{n}\equiv b\pmod{n} }[/math], то имеем [math]\displaystyle{ b^{n}\equiv b\pmod{p} }[/math], и так как [math]\displaystyle{ b }[/math] и [math]\displaystyle{ p }[/math] – взаимнопростые числа, то [math]\displaystyle{ b^{n-1}\equiv 1\pmod{p} }[/math]. Из того, что порядок примитивного элемента [math]\displaystyle{ b\pmod{p} }[/math] в группе [math]\displaystyle{ (\mathbb{Z}/p\mathbb{Z})^* }[/math] равен [math]\displaystyle{ p - 1 }[/math], следует, что [math]\displaystyle{ p - 1 \mid n - 1 }[/math].
С другой стороны, предположим, что [math]\displaystyle{ n }[/math] свободно от квадратов и [math]\displaystyle{ p - 1 \mid n - 1 }[/math] для любого простого [math]\displaystyle{ p | n }[/math]. Пусть [math]\displaystyle{ p }[/math] — некоторое простое число, делящее [math]\displaystyle{ n }[/math], и число [math]\displaystyle{ b }[/math] – целое.
Из малой теоремы Ферма следует, что если [math]\displaystyle{ p }[/math] – простое, а [math]\displaystyle{ b }[/math] – целое, то [math]\displaystyle{ b^{k}\equiv b\pmod{p} }[/math] для любого положительного целого [math]\displaystyle{ k }[/math], такого что [math]\displaystyle{ p - 1 \mid k - 1 }[/math]. (Пусть [math]\displaystyle{ q\cdot (p-1) = (k-1) }[/math], где [math]\displaystyle{ q }[/math] — положительное целое число. Так как [math]\displaystyle{ b^{p} \equiv b\cdot b^{p-1} \equiv b \pmod p, b^{p-1} \equiv 1 \pmod p }[/math], поэтому [math]\displaystyle{ b\cdot b^{p-1}\cdot b^{p-1}\cdot \ldots \cdot b^{p-1} \equiv b\cdot b^{q\cdot(p-1)}\equiv b\cdot b^{k-1} \equiv b^{k} \equiv b \pmod p }[/math])
Тогда для частного случая [math]\displaystyle{ k=n }[/math] мы имеем, что [math]\displaystyle{ b^n- b }[/math] делится на любой простой делитель числа [math]\displaystyle{ n }[/math], так как [math]\displaystyle{ n }[/math] свободно от квадратов, то [math]\displaystyle{ b^n- b }[/math] делится на [math]\displaystyle{ n }[/math], то есть [math]\displaystyle{ b^{n}\equiv b\pmod{n} }[/math]. Таким образом теорема Корсельта доказана.
Корсельт оставил открытым вопрос поиска составных чисел, удовлетворяющих этому критерию. В 1910 году Кармайкл сформулировал критерий, по существу совпадающий с критерием Корсельта, и дал пример составного числа [math]\displaystyle{ n }[/math], для которого он выполняется — [math]\displaystyle{ n = 561 }[/math]. Это число раскладывается на простые множители как 561 = 3·11·17, и поэтому свободно от квадратов, в то время как [math]\displaystyle{ 561-1=560 }[/math] делится на 2, 10 и 16. После чего все контрпримеры получили наименование чисел Кармайкла.
В частности, из теоремы Корсельта следует, что все числа Кармайкла нечётны, так как любое чётное составное число, свободное от квадратов, имеет по крайней мере один нечётный простой делитель, и поэтому из делимости [math]\displaystyle{ p - 1 \mid n - 1 }[/math] следует, что чётное делит нечётное, что невозможно.
В 1939 году Джон Черник доказал теорему, которая может быть использована для построения подмножества чисел Кармайкла: если [math]\displaystyle{ 6m+1 }[/math], [math]\displaystyle{ 12m+1 }[/math], [math]\displaystyle{ 18m+1 }[/math] — простые числа для одного натурального [math]\displaystyle{ m }[/math], то их произведение [math]\displaystyle{ M_3 (m)=(6m+1)(12m+1)(18m+1) }[/math] является числом Кармайкла[2]. Это условие может быть удовлетворено, только если число [math]\displaystyle{ m }[/math] заканчивается цифрами 0, 1, 5 или 6 по основанию 10, то есть [math]\displaystyle{ m }[/math] сравнимо с 0 или 1 по модулю 5. Например, для [math]\displaystyle{ m=1 }[/math] множители равны соответственно [math]\displaystyle{ 7 }[/math], [math]\displaystyle{ 13 }[/math] и [math]\displaystyle{ 19 }[/math], а их произведение даёт число Кармайкла 1729.
Способ нахождения чисел Кармайкла, предложенный Черником, может быть расширен на количество множителей [math]\displaystyle{ k\geqslant3 }[/math]:
- [math]\displaystyle{ M_k(m) = (6m+1)(12m+1)\prod^{k-2}_{i=1}(9\cdot2^{i}m+1),\quad k\geqslant3 }[/math],
при условии, что все множители простые и [math]\displaystyle{ m }[/math] делится на [math]\displaystyle{ 2^{k-4} }[/math].
Гипотезу о бесконечности таких чисел высказал ещё Кармайкл в 1912 году, теорема Черника умозрительно повысила вероятность её выполнения; позднее Пал Эрдёш эвристически обосновал бесконечность чисел Кармайкла. Однако только в 1992 году[2] это утверждение было строго доказано Уильямом Алфордом, Эндрю Грэнвиллом и Карлом Померансом[1], точнее: доказано, что между 1 и достаточно большим [math]\displaystyle{ n }[/math] содержится [math]\displaystyle{ n^{2/7} }[/math] чисел Кармайкла.
В 1992 году Гюнтер Лё И Вольфганг Нибур предложили новый алгоритм для построения больших чисел Кармайкла: удалось найти число, получаемое перемножением 1 101 518 простых чисел; это число содержит 16 142 049 цифр[3].
Свойства
Теоремы Бигера и Дюпарка
В 1956 году Бигер доказал, что если для простых чисел [math]\displaystyle{ p }[/math], [math]\displaystyle{ q }[/math] и [math]\displaystyle{ r }[/math] выполняется соотношение [math]\displaystyle{ p\lt q\lt r }[/math] и [math]\displaystyle{ pqr }[/math] — число Кармайкла, то [math]\displaystyle{ q\lt 2p^2 }[/math] и [math]\displaystyle{ r\lt p^3 }[/math]. Таким образом, количество чисел Кармайкла, получаемых произведением трёх простых множителей, один из которых известен, конечно.
Дюпарк позже обобщил этот результат, чтобы показать, что если [math]\displaystyle{ n=mqr }[/math] — число Кармайкла, где [math]\displaystyle{ q }[/math] и [math]\displaystyle{ r }[/math] — простые, тогда [math]\displaystyle{ q\lt 2m^2 }[/math] и [math]\displaystyle{ r\lt m^3 }[/math]. Следовательно, существует не более чем конечное количество чисел Кармайкла со всеми, кроме двух, определёнными множителями.
Случай [math]\displaystyle{ m }[/math] = 1 показывает, что любое кармайклово число содержит как минимум 3 простых множителя, к этому выводу впервые пришёл сам Кармайкл.
Разложения на простые множители
Разложения первых нескольких чисел Кармайкла на простые множители таковы:
- [math]\displaystyle{ \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]\displaystyle{ k = 3, 4, 5, \ldots }[/math] простыми множителями[4]:
k | |
---|---|
3 | [math]\displaystyle{ 561 = 3 \cdot 11 \cdot 17 }[/math] |
4 | [math]\displaystyle{ 41041 = 7 \cdot 11 \cdot 13 \cdot 41 }[/math] |
5 | [math]\displaystyle{ 825265 = 5 \cdot 7 \cdot 17 \cdot 19 \cdot 73 }[/math] |
6 | [math]\displaystyle{ 321197185 = 5 \cdot 19 \cdot 23 \cdot 29 \cdot 37 \cdot 137 }[/math] |
7 | [math]\displaystyle{ 5394826801 = 7 \cdot 13 \cdot 17 \cdot 23 \cdot 31 \cdot 67 \cdot 73 }[/math] |
8 | [math]\displaystyle{ 232250619601 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 31 \cdot 37 \cdot 73 \cdot 163 }[/math] |
9 | [math]\displaystyle{ 9746347772161 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 31 \cdot 37 \cdot 41 \cdot 641 }[/math] |
Первые кармайкловы числа с четырьмя простыми множителями[5]:
i | |
---|---|
1 | [math]\displaystyle{ 41041 = 7 \cdot 11 \cdot 13 \cdot 41 }[/math] |
2 | [math]\displaystyle{ 62745 = 3 \cdot 5 \cdot 47 \cdot 89 }[/math] |
3 | [math]\displaystyle{ 63973 = 7 \cdot 13 \cdot 19 \cdot 37 }[/math] |
4 | [math]\displaystyle{ 75361 = 11 \cdot 13 \cdot 17 \cdot 31 }[/math] |
5 | [math]\displaystyle{ 101101 = 7 \cdot 11 \cdot 13 \cdot 101 }[/math] |
6 | [math]\displaystyle{ 126217 = 7 \cdot 13 \cdot 19 \cdot 73 }[/math] |
7 | [math]\displaystyle{ 172081 = 7 \cdot 13 \cdot 31 \cdot 61 }[/math] |
8 | [math]\displaystyle{ 188461 = 7 \cdot 13 \cdot 19 \cdot 109 }[/math] |
9 | [math]\displaystyle{ 278545 = 5 \cdot 17 \cdot 29 \cdot 113 }[/math] |
10 | [math]\displaystyle{ 340561 = 13 \cdot 17 \cdot 23 \cdot 67 }[/math] |
Распределение
Следующая таблица показывает количество [math]\displaystyle{ C(X) }[/math] чисел Кармайкла меньше или равных числу [math]\displaystyle{ X }[/math], которое задаётся как степень [math]\displaystyle{ n }[/math] десяти:[6]
[math]\displaystyle{ n }[/math] | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
[math]\displaystyle{ C(10^n) }[/math] | 0 | 0 | 1 | 7 | 16 | 43 | 105 | 255 | 646 | 1547 | 3605 | 8241 | 19279 | 44706 | 105212 | 246683 |
В 1953 году Вальтер Кнёдель доказал, что:
- [math]\displaystyle{ C(X) \lt X \exp\left({-k_1 \left( \log X \log \log X\right)^\frac{1}{2}}\right) }[/math]
для некоторой константы [math]\displaystyle{ k_1 }[/math].
Пусть [math]\displaystyle{ C(X) }[/math] обозначает количество чисел Кармайкла, меньших [math]\displaystyle{ X }[/math]. Эрдёш доказал в 1956 году, что
- [math]\displaystyle{ C(X) \lt X \exp{\frac{-k_2 \log{X} \log{\log{\log{X}}}}{\log{\log{X}}}} }[/math]
для некоторой константы [math]\displaystyle{ k_2 }[/math]. При этом также доказано[1], что существует бесконечно много чисел Кармайкла, то есть, [math]\displaystyle{ \lim_{X\to\infty} C(X) = \infty }[/math].
В следующей таблице приведены приближённые минимальные значения константы k для значений X = 10n при разных n:
[math]\displaystyle{ 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) является числом Рамануджана — Харди (наименьшее число, представимое в виде суммы двух кубов двумя способами).
Примечания
- ↑ 1,0 1,1 1,2 W. R. Alford, A. Granville, C. Pomerance. There are Infinitely Many Carmichael Numbers (англ.) // Annals of Mathematics : journal. — 1994. — Vol. 139. — P. 703—722. — doi:10.2307/2118576.
- ↑ 2,0 2,1 2,2 2,3 C. Pomerance. Carmichael numbers (неопр.) // Nieuw Arch. Wisk.. — 1993. — С. 199—209.
- ↑ G Löh, W. Niebuhr. A new algorithm for constructing large Carmichael numbers (англ.) // Math. Comp. : journal. — 1996. — Vol. 65, no. 214. — P. 823—836.
- ↑ последовательность A006931 в OEIS
- ↑ последовательность A074379 в OEIS
- ↑ Richard Pinch. "The Carmichael numbers up to 10^21" (2007).