Число Кармайкла (Cnvlk Tgjbgwtlg)

Перейти к навигации Перейти к поиску

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

Названы по имени американского математика Роберта Кармайкла.

Общие сведения

[править | править код]

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

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

Первым, кто открыл числовые свойства, которые впоследствии стали характеристикой чисел Кармайкла, был Алвин Корсельт, доказавшим в 1899 году теорему о целых числах, эквивалентную условиям обращения малой теоремы Ферма, то есть для целых чисел , для которых выполняется при любых целых : составное число является числом Кармайкла тогда и только тогда, когда свободно от квадратов и для каждого простого делителя числа число делит число [2].

Корсельт оставил открытым вопрос поиска составных чисел, удовлетворяющих этому критерию. В 1910 году Кармайкл сформулировал критерий, по существу совпадающий с критерием Корсельта, и дал пример составного числа , для которого он выполняется — . Это число раскладывается на простые множители как 561 = 3·11·17, и поэтому свободно от квадратов, в то время как делится на 2, 10 и 16. После чего все контрпримеры получили наименование чисел Кармайкла.

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

В 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 простых множителя, к этому выводу впервые пришёл сам Кармайкл.

Разложения на простые множители

[править | править код]

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

Кармайкловы числа имеют по меньшей мере три простых положительных множителя. Первые кармайкловы числа с простыми множителями[4]:

k  
3
4
5
6
7
8
9

Первые кармайкловы числа с четырьмя простыми множителями[5]:

i  
1
2
3
4
5
6
7
8
9
10

Распределение

[править | править код]

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

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. There are Infinitely Many Carmichael Numbers (англ.) // Annals of Mathematics : journal. — 1994. — Vol. 139. — P. 703—722. — doi:10.2307/2118576. Архивировано 4 марта 2005 года.
  2. 1 2 3 4 C. Pomerance. Carmichael numbers (неопр.) // Nieuw Arch. Wisk.. — 1993. — С. 199—209. Архивировано 7 февраля 2015 года.
  3. G Löh, W. Niebuhr. A new algorithm for constructing large Carmichael numbers (англ.) // Math. Comp.[англ.] : journal. — 1996. — Vol. 65, no. 214. — P. 823—836. Архивировано 7 февраля 2015 года.
  4. последовательность A006931 в OEIS
  5. последовательность A074379 в OEIS
  6. Richard Pinch. "The Carmichael numbers up to 10^21" (2007). Дата обращения: 9 февраля 2015. Архивировано 8 августа 2014 года.