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

Число Кармайкла — додатне складене число n, що задовольняє умову ${\displaystyle \ b^{n-1}\equiv 1{\pmod {n}}}$ для всіх цілих b, взаємно простих з n.

Названі на честь американського математика Роберта Кармайкла^[en], що у 1910 році знайшов перше і найменше таке число, 561.

Загальне уявлення

Мала теорема Ферма стверджує, що будь-яке просте число задовольняє вище вказану властивість. У цьому сенсі числа Кармайкла подібні простим. Тому вони називаються псевдопростими числами.

Еквівалентне визначення чисел Кармайкла дає критерій Корсельта.

Теорема (Корсельт, 1899) : Складене число n є числом Кармайкла тоді і тільки тоді, коли n вільне від квадратів і для всіх простих дільників p числа n вірно p − 1 | n − 1 (позначення а | b означає, що а ділить b).

З цієї теореми випливає, що всі числа Кармайкла непарні, оскільки будь-яке парне складене число, вільне від квадратів, має принаймні одного непарного простого дільника, і тому з p − 1 | n − 1 випливає, що парне ділить непарне, що невірно - суперечність.

Такі числа Кармайкла:

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

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

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

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

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

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

У 1994 році Альфорс, Ґренвіл і Померанс довели, що для достатньо великих чисел n кількість чисел Кармайкла, що не перевищують n є не меншою n^2 / 7. Звідси зокрема випливає нескінченність множини цих чисел.

Властивості

Числа Кармайкла мають щонайменше три прості додатні множники. Нижче подані найменші такі числа з ${\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}$

Перші числа Кармайкла з чотирма простими множниками:

i
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}$

Розподіл

Нехай ${\displaystyle C(X)}$ позначає кількість чисел Кармайкла, менших за ${\displaystyle X}$. Ердеш довів у 1956 році, що

${\displaystyle C(X)<X\exp {\frac {-k\log {X}\log {\log {\log {X}}}}{\log {\log {X}}}}}$

для деякої константи ${\displaystyle k}$;

У наступній таблиці наведені наближені значення цієї константи:

n	k
10^4	2.19547
10^6	1.97946
10^8	1.90495
10^10	1.86870
10^12	1.86377
10^14	1.86293
10^16	1.86406
10^18	1.86522
10^20	1.86598

Цікаві факти

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

Джерела

• Chernick, J. (1935). On Fermat's simple theorem. Bull. Amer. Math. Soc. 45, 269–274.
• Ribenboim, Paolo (1996). The New Book of Prime Number Records.
• Löh, Günter and Niebuhr, Wolfgang (1996). A new algorithm for constructing large Carmichael numbers(pdf)
• Korselt (1899). Problème chinois. L'intermédiaire des mathématiciens, 6, 142–143.
• Carmichael, R. D. (1912) On composite numbers P which satisfy the Fermat congruence ${\displaystyle a^{P-1}\equiv 1{\bmod {P}}}$. Am. Math. Month. 19 22–27.
• Erdős, Paul (1956). On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4, 201 –206.