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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Число Кармайкла — додатне складене число 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.