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

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

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

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

Загальне уявлення[ред.ред. код]

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

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

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

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

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

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).

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

Властивості[ред.ред. код]

Числа Кармайкла мають щонайменше три прості додатні множники. Нижче подані найменші такі числа з k = 3, 4, 5, \ldots простими множниками:

k  
3 561 = 3 \cdot 11 \cdot 17
4 41041 = 7 \cdot 11 \cdot 13 \cdot 41
5 825265 = 5 \cdot 7 \cdot 17 \cdot 19 \cdot 73
6 321197185 = 5 \cdot 19 \cdot 23 \cdot 29 \cdot 37 \cdot 137
7 5394826801 = 7 \cdot 13 \cdot 17 \cdot 23 \cdot 31 \cdot 67 \cdot 73
8 232250619601 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 31 \cdot 37 \cdot 73 \cdot 163
9 9746347772161 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 31 \cdot 37 \cdot 41 \cdot 641

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

i  
1 41041 = 7 \cdot 11 \cdot 13 \cdot 41
2 62745 = 3 \cdot 5 \cdot 47 \cdot 89
3 63973 = 7 \cdot 13 \cdot 19 \cdot 37
4 75361 = 11 \cdot 13 \cdot 17 \cdot 31
5 101101 = 7 \cdot 11 \cdot 13 \cdot 101
6 126217 = 7 \cdot 13 \cdot 19 \cdot 73
7 172081 = 7 \cdot 13 \cdot 31 \cdot 61
8 188461 = 7 \cdot 13 \cdot 19 \cdot 109
9 278545 = 5 \cdot 17 \cdot 29 \cdot 113
10 340561 = 13 \cdot 17 \cdot 23 \cdot 67

Розподіл[ред.ред. код]

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

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

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

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

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 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.