Число Кармайкла
Число Кармайкла — составное число , которое удовлетворяет сравнению для всех целых , взаимно простых с , другими словами — псевдопростое число по каждому основанию , взаимно простому с . Такие числа относительно редки, но их бесконечное число, наименьшее из них — 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 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.
- ↑ 1 2 3 4 C. Pomerance. Carmichael numbers (неопр.) // Nieuw Arch. Wisk.. — 1993. — С. 199—209.
- ↑ G Löh, W. Niebuhr. A new algorithm for constructing large Carmichael numbers (англ.) // Math. Comp. (англ.) (рус. : journal. — 1996. — Vol. 65, no. 214. — P. 823—836.
- ↑ последовательность A006931 в OEIS
- ↑ последовательность A074379 в OEIS
- ↑ Richard Pinch. "The Carmichael numbers up to 10^21" (неопр.) (2007).