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

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

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

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

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

Малая теорема Ферма утверждает, что если — простое число и — целое число, не делящееся на , то  делится на , т.е.  . Числа Кармайкла являются составными, при этом для них выполняется данное соотношение. Числа Кармайкла также называют абсолютно псевдопростыми числами Ферма, так как они являются псевдопростыми числами Ферма по каждому взаимно простому с ними основанию.

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

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

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

Теорема (Критерий Корсельта)

Составное число является числом Кармайкла тогда и только тогда, когда свободно от квадратов и для каждого простого делителя числа число делит число [2].



Корсельт оставил открытым вопрос поиска составных чисел, удовлетворяющих этому критерию. В 1910 году Кармайкл сформулировал критерий, по существу совпадающий с критерием Корсельта, и дал пример составного числа , для которого он выполняется. Первым таким числом было . Это число раскладывается на простые множители как 561 = 3·11·17, и поэтому свободно от квадратов, в то время как делится на 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 (1993). «Carmichael numbers». Nieuw Arch. Wisk.: 199–209.
  3. G Löh, W. Niebuhr (1996). «A new algorithm for constructing large Carmichael numbers». Math. Comp. (214): 823-836.
  4. Richard Pinch. "The Carmichael numbers up to 10^21" (2007).