Это не официальный сайт wikipedia.org 01.01.2023

Число Кармайкла — Википедия

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

(перенаправлено с «Числа Кармайкла»)

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

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

Общие сведенияПравить

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

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

ИсторияПравить

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

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

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

В 1939 году Джон Черник доказал теорему, которая может быть использована для построения подмножества чисел Кармайкла: если 6 m + 1  , 12 m + 1  , 18 m + 1   — простые числа для одного натурального m  , то их произведение M 3 ( m ) = ( 6 m + 1 ) ( 12 m + 1 ) ( 18 m + 1 )   является числом Кармайкла[2]. Это условие может быть удовлетворено, только если число m   заканчивается цифрами 0, 1, 5 или 6 по основанию 10, то есть m   сравнимо с 0 или 1 по модулю 5. Например, для m = 1   множители равны соответственно 7  , 13   и 19  , а их произведение даёт число Кармайкла 1729.

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

M k ( m ) = ( 6 m + 1 ) ( 12 m + 1 ) i = 1 k 2 ( 9 2 i m + 1 ) , k 3  ,

при условии, что все множители простые и 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   и p q r   — число Кармайкла, то q < 2 p 2   и r < p 3  . Таким образом, количество чисел Кармайкла, получаемых произведением трёх простых множителей, один из которых известен, конечно.

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

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

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

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

561 = 3 11 17 ( 2 560 ; 10 560 ; 16 560 ) , 1105 = 5 13 17 ( 4 1104 ; 12 1104 ; 16 1104 ) , 1729 = 7 13 19 ( 6 1728 ; 12 1728 ; 18 1728 ) , 2465 = 5 17 29 ( 4 2464 ; 16 2464 ; 28 2464 ) , 2821 = 7 13 31 ( 6 2820 ; 12 2820 ; 30 2820 ) , 6601 = 7 23 41 ( 6 6600 ; 22 6600 ; 40 6600 ) , 8911 = 7 19 67 ( 6 8910 ; 18 8910 ; 66 8910 ) .  

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

k  
3 561 = 3 11 17  
4 41041 = 7 11 13 41  
5 825265 = 5 7 17 19 73  
6 321197185 = 5 19 23 29 37 137  
7 5394826801 = 7 13 17 23 31 67 73  
8 232250619601 = 7 11 13 17 31 37 73 163  
9 9746347772161 = 7 11 13 17 19 31 37 41 641  

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

i  
1 41041 = 7 11 13 41  
2 62745 = 3 5 47 89  
3 63973 = 7 13 19 37  
4 75361 = 11 13 17 31  
5 101101 = 7 11 13 101  
6 126217 = 7 13 19 73  
7 172081 = 7 13 31 61  
8 188461 = 7 13 19 109  
9 278545 = 5 17 29 113  
10 340561 = 13 17 23 67  

РаспределениеПравить

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

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 ( k 1 ( log X log log X ) 1 2 )  

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

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

C ( X ) < X exp k 2 log X log log log X log log X  

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

В следующей таблице приведены приближённые минимальные значения константы 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. There are Infinitely Many Carmichael Numbers (англ.) // Annals of Mathematics : journal. — 1994. — Vol. 139. — P. 703—722. — doi:10.2307/2118576.
  2. 1 2 3 4 C. Pomerance. Carmichael numbers (неопр.) // Nieuw Arch. Wisk.. — 1993. — С. 199—209.
  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.
  4. последовательность A006931 в OEIS
  5. последовательность A074379 в OEIS
  6. Richard Pinch. "The Carmichael numbers up to 10^21"  (неопр.) (2007).