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

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

В теории чисел числом Кармайкла (кармайкловым числом, англ. Carmichael number) называется всякое составное число , которое удовлетворяет сравнению для всех целых , взаимно простых с . Другими словами, числом Кармайкла называется составное число , которое является псевдопростым числом по каждому основанию , взаимно простому с .

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

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

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

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

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

Теорема (Критерий Корсельта): Положительное целое удовлетворяет условию для любых целых тогда и только тогда, когда свободно от квадратов и для каждого простого делителя числа число делит число .[2]


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

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

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

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

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

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

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

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

Обобщение метода Черника
Способ нахождения чисел Кармайкла, предложенный Черником, может быть расширен на количество множителей : при условии что все множители простые и делится на

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

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

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

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

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

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

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

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

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

Кармайкловы числа имеют по меньшей мере три простых положительных множителя. Первые Кармайкловы числа с простыми множителями (последовательность A006931 в OEIS):

k  
3
4
5
6
7
8
9

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

i  
1
2
3
4
5
6
7
8
9
10

Распределение[править | править вики-текст]

Следующая таблица показывает количество чисел Кармайкла меньше или равных числу , которое задается как степень десяти:[4]

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

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

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

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

для некоторой константы . При этом также доказано,[1] что существует бесконечно много чисел Кармайкла, то есть, .

В следующей таблице приведены приближенные минимальные значения константы k для значений X = 10n при разных 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).