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

Число Кармайкла — додатне складене число n, що задовольняє умову для всіх цілих b, взаємно простих з n.

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

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

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

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

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

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

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

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

Властивості

Числа Кармайкла мають щонайменше три прості додатні множники. Нижче подані найменші такі числа з простими множниками:

k  
3
4
5
6
7
8
9

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

i  
1
2
3
4
5
6
7
8
9
10

Розподіл

Нехай позначає кількість чисел Кармайкла, менших за . Ердеш довів у 1956 році, що

для деякої константи ;

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

n k
104 2.19547
106 1.97946
108 1.90495
1010 1.86870
1012 1.86377
1014 1.86293
1016 1.86406
1018 1.86522
1020 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 . Am. Math. Month. 19 22–27.
  • Erdős, Paul (1956). On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4, 201 –206.