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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории чисел числом Кармайкла (кармайкловым числом, англ. Carmichael number) называется всякое составное число n, которое удовлетворяет сравнению b^{n-1}\equiv 1\pmod{n} для всех целых b, взаимно простых с n. Другими словами, числом Кармайкла называется составное число n, которое является псевдопростым числом по каждому основанию b, взаимно простому с n.

Своё название числа Кармайкла получили в честь американского математика Роберта Кармайкла.

Общие сведения[править | править вики-текст]

Малая теорема Ферма утверждает, что если n — простое число и b — целое число, не делящееся на n, то  b^{n-1}-1 делится на n, т.е  b^{n}\equiv b\pmod{n}. Числа Кармайкла являются составными, при этом для них выполняется данное соотношение. Числа Кармайкла также называют абсолютно псевдопростыми Ферма, так как они являются псевдопростыми Ферма по каждому взаимно простому с ними основанию. Существование чисел Кармайкла делает тест простоты Ферма менее эффективным для обнаружения простых чисел, по сравнению например с более строгим Тестом Соловея — Штрассена, который распознает эти числа как составные. С ростом чисел, числа Кармайкла становятся очень редкими. Например в промежутке от 1 до 1021 их содержится 20,138,200 (примерно одно на 50 триллионов (5*1013) чисел), тем не менее доказано, что чисел Кармайкла бесконечно много.[1]

История открытия[править | править вики-текст]

Первым, кто открыл числовые свойства, которые впоследствии стали характеристикой чисел Кармайкла был Алвин Корсельт. В 1899г. Корсельтом была доказана теорема(критерий) о целых числах, эквивалентная условиям обращения малой теоремы Ферма, т.е. для целых чисел n, для которых выполняется b^{n}\equiv b\pmod{n} при любых целых b.

Теорема (Критерий Корсельта): Положительное целое  n удовлетворяет условию b^{n}\equiv b\pmod{n} для любых целых b тогда и только тогда, когда n свободно от квадратов и для каждого простого делителя p числа n число число p - 1 делит число n-1.[2]

Однако Корсельт оставил открытым вопрос поиска составных чисел, удовлетворяющих этому критерию. И в 1910 году Кармайкл сформулировал критерий, по существу совпадающий с критерием Корсельта и дал пример составного числа n, для которого он выполняется. Первым таким числом было n = 561. Легко проверить что число 561 имеет разложение на простые множители 3*11*17, свободно от квадратов и 560 делится на 2, 10 и 16. Таким образом обратное утверждение малой теоремы Ферма для любых оснований b неверно, с тех пор как существует контрпример 561. Такие контрпримеры стали называть числами Кармайкла.

Теперь критерий Корсельта для составных чисел считается эквивалентным определением чисел Кармайкла – составное число является числом Кармайкла тогда и только тогда, когда оно удовлетворяет критерию Корсельта.

В частности, из теоремы Корсельта следует, что все числа Кармайкла нечётны, так как любое чётное составное число, свободное от квадратов, имеет по крайней мере один нечётный простой делитель, и поэтому из делимости  p - 1 | n - 1 следует, что чётное делит нечётное, что невозможно.

Дальнейшее развитие[править | править вики-текст]

В 1939 году Джон Черник доказал теорему, которая может быть использована для построения подмножества чисел Кармайкла:

Теорема(Черник, 1939) Если 6m+1, 12m+1, 18m+1 – простые числа для одного натурального m, то их произведение M_3 (m)=(6m+1)(12m+1)(18m+1) является числом Кармайкла.[2]

Это условие может быть удовлетворено только если число m заканчивается цифрами 0, 1, 5 или 6 по основанию 10, т.е m соответствует 0 или 1 по модулю 5.

Например для m=1 множители равны соответственно 7, 13 и 19
, из произведение дает число Кармайкла 1729.

Обобщение метода Черника
Способ нахождения чисел Кармайкла, предложенный Черником, может быть расширен на количество множителей k\ge3:M_k(m) = (6m+1)(12m+1)\prod^{k-2}_{i=1}(9\cdot2^{i}m+1), k\ge3, при условии что все множители простые и m делится на 2^{k-4}

Теорема Черника наводит на мысль о том, что чисел Кармайкла бесконечно много, хотя еще в 1912 году сам Кармайкл предположил это. В дальнейшем Пал Эрдеш эвристически показал бесконечность количества чисел Кармайкла. Однако только в 1992[2] году это было строго доказано Вильямом Алфордом, Эндрю Грэнвиллом и Карлом Померансом в совместной работе[1]. А именно, они показали, что между 1 и достаточно большим n содержится n^{2/7} чисел Кармайкла.

В 1992 году Гюнтер Лё И Вольфганг Нибур представили новый алгоритм для построения больших чисел Кармайкла. Им удалось найти число, получаемое перемножением 1,101,518 простых чисел, это число содержит 16,142,049 цифр.[3]

Свойства[править | править вики-текст]

Теоремы Бигера и Дюпарка[править | править вики-текст]

В 1956 году Н. Бигер доказал, что если для простых чисел p, q и r выполняется соотношение p<q<r и pqr – число Кармайкла, то q<2p^2 и r<p^3. Таким образом, количество чисел Кармайкла, получаемых произведением трех простых множителей, один из которых известен, конечно.

Дюпарк позже обобщил этот результат чтобы показать, что если n=mqr – число Кармайкла, где q и r – простые, тогда q<2m^2 и r<m^3. Следовательно существует не более чем конечное количество чисел Кармайкла со всеми, кроме двух, определенными множителями.

Случай m = 1 показывает, что любое кармайклово число содержит как минимум 3 простых множителя, к этому выводу впервые пришел сам Кармайкл.

Разложения на простые множители[править | править вики-текст]

Разложения первых нескольких чисел Кармайкла на простые множители таковы:

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

Кармайкловы числа имеют по меньшей мере три простых положительных множителя. Первые Кармайкловы числа с k = 3, 4, 5, \ldots простыми множителями (последовательность A006931 в OEIS):

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

Первые кармайкловы числа с четырьмя простыми множителями (последовательность A074379 в OEIS):

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, которое задается как степень n десяти:[4]

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
C(10^n) 0 0 1 7 16 43 105 255 646 1547 3605 8241 19279 44706 105212 246683

В 1953 году Вальтер Кнёдель доказал, что

C(X) < X \exp\left({-k_1 \left( \log X \log \log X\right)^\frac{1}{2}}\right)

для некоторой константы k_1

Пусть C(X) обозначает количество чисел Кармайкла, меньших X. Эрдёш доказал в 1956 году, что

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

для некоторой константы k_2. При этом также доказано,[1] что существует бесконечно много чисел Кармайкла, то есть, \lim_{X\to\infty} C(X) = \infty.

В следующей таблице приведены приближенные минимальные значения константы k для значений X = 10n при разных n:

n 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. 1 2 3 W. R. Alford, A. Granville, C. Pomerance (1994). «There are Infinitely Many Carmichael Numbers». Annals of Mathematics 139: 703-722. DOI:10.2307/2118576.
  2. 1 2 3 4 C. Pomerance. Carmichael numbers 199–209. Nieuw Arch. Wisk. (1993).
  3. G.LOH AND W.NIEBUHR. [http://www.ams.org/journals/mcom/1996-65-214/S0025-5718-96-00692-8/S0025-5718-96-00692-8.pdf A NEW ALGORITHM FOR CONSTRUCTING LARGE CARMICHAEL NUMBERS] 823-836. Math. Comp. (1996).
  4. Richard Pinch. "The Carmichael numbers up to 10^21" (2007).