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


В теории чисел числом Кармайкла кармайкловым числом, англ Carmichael number называется всякое составное число n , которое удовлетворяет сравнению b n − 1 ≡ 1 mod n \equiv 1 для всех целых b , взаимно простых с n Другими словами, числом Кармайкла называется составное число n , которое является псевдопростым числом по каждому основанию b , взаимно простому с n

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

Содержание

  • 1 Общие сведения
  • 2 История открытия
  • 3 Дальнейшее развитие
  • 4 Свойства
    • 41 Теоремы Бигера и Дюпарка
    • 42 Разложения на простые множители
    • 43 Распределение
  • 5 Интересные факты
  • 6 Примечания

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

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

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

История открытияправить

Первым, кто открыл числовые свойства, которые впоследствии стали характеристикой чисел Кармайкла, был Алвин Корсельт В 1899 году Корсельтом была доказана теорема критерий о целых числах, эквивалентная условиям обращения малой теоремы Ферма, те для целых чисел n , для которых выполняется b n ≡ b mod n \equiv b при любых целых b

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

Составное число n является числом Кармайкла тогда и только тогда, когда n свободно от квадратов и для каждого простого делителя p числа n число p − 1 делит число  n − 1 2

Доказательство теоремы Корсельта2  

Пусть, что b n ≡ b mod n \equiv b для всех целых b Сначала докажем, что число n должно быть свободно от квадратов Предположим, что это не так и k 2 | n |n k 2 делит n для некоторого целого k > 1 Пусть b = k , тогда k n ≡ k mod n \equiv k Так как k 2 | n |n , то это соотношение верно по модулю k 2 , то есть k n ≡ k mod k 2 \equiv k , что противоречит выражению k n ≡ 0 mod k 2 \equiv 0 Таким образом, число n свободно от квадратов Пусть теперь p – простой делитель числа n Известно, что мультипликативная группа Z / p Z ∗ /p\mathbb ^ кольца вычетов по модулю p , где p – простое, является циклической группой порядка p − 1 Пусть b – целое число, такое, что b mod p – генератор группы Z / p Z ∗ /p\mathbb ^ Так как b n ≡ b mod n \equiv b , то имеем b n ≡ b mod p \equiv b , и так как b и p – взаимнопростые числа, то b n − 1 ≡ 1 mod p \equiv 1 Из того, что порядок примитивного элемента b mod p в группе Z / p Z ∗ /p\mathbb ^ равен p − 1 , следует, что p − 1 | n − 1

С другой стороны, предположим, что n - свободно от квадратов и p − 1 | n − 1 для любого простого p | n Пусть p – некоторое простое число, делящее n , и число b – целое

Из малой теоремы Ферма следует, что если p – простое, а b – целое, то b k ≡ b mod p \equiv b для любого положительного целого k , такого что p − 1 | k − 1 Пусть q ⋅ p − 1 = k − 1 , где q – положительное целое число Так как b p ≡ b ⋅ b p − 1 ≡ b mod p , b p − 1 ≡ 1 mod p \equiv b\cdot b^\equiv b,b^\equiv 1 , поэтому b ⋅ b p − 1 ⋅ b p − 1 ⋅ ⋅ b p − 1 ≡ b ⋅ b q ⋅ p − 1 ≡ b ⋅ b k − 1 ≡ b k ≡ b mod p \cdot b^\cdot \cdot b^\equiv b\cdot b^\equiv b\cdot b^\equiv b^\equiv b

Тогда для частного случая k = n мы имеем, что b n − b -b делится на любой простой делитель числа n , так как n - свободно от квадратов, то b n − b -b делится на n , то есть b n ≡ b mod n \equiv b Таким образом теорема Корсельта доказана


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

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

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

Дальнейшее развитиеправить

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

Теорема Черник, 1939

Если 6 m + 1 , 12 m + 1 , 18 m + 1  — простые числа для одного натурального m , то их произведение M 3 m = 6 m + 1 12 m + 1 18 m + 1 m=6m+112m+118m+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=6m+112m+1\prod _^9\cdot 2^m+1,\quad k\geqslant 3,

при условии, что все множители простые и m делится на 2 k − 4

Теорема Черника наводит на мысль о том, что чисел Кармайкла бесконечно много, хотя ещё в 1912 году сам Кармайкл предположил это В дальнейшем Пал Эрдёш эвристически показал бесконечность количества чисел Кармайкла Однако только в 19922 году это было строго доказано Вильямом Алфордом, Эндрю Грэнвиллом и Карлом Померансом в совместной работе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 , … простыми множителями последовательность A006931 в OEIS:

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

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

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 десяти:4

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 \left\log X\log \log X\right^\right

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

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

C X < X exp ⁡ − k 2 log ⁡ X log ⁡ log ⁡ log ⁡ X log ⁡ log ⁡ X \log \log

для некоторой константы k 2 При этом также доказано1, что существует бесконечно много чисел Кармайкла, то есть, lim X → ∞ C X = ∞ CX=\infty

В следующей таблице приведены приближённые минимальные значения константы k для значений X = 10n при разных n:

n 4 6 8 10 12 14 16 18 20 21
k 219547 197946 190495 186870 186377 186293 186406 186522 186598 186619

Интересные фактыправить

  • Второе кармайклово число 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:102307/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


Число Кармайкла Информацию О

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


  • user icon

    Число Кармайкла beatiful post thanks!

    29.10.2014


Число Кармайкла
Число Кармайкла
Число Кармайкла Вы просматриваете субъект
Число Кармайкла что, Число Кармайкла кто, Число Кармайкла описание

There are excerpts from wikipedia on this article and video

Случайные Статьи

Анна-Павловна

Анна-Павловна

Анна-Павловна (нидерл. Anna Paulowna) — община и город в Нидерландах, в провинции Северная...
Белоспинный лори

Белоспинный лори

Систематика на Викивидах Изображения на Викискладе ITIS 554806 NCBI 176072 Межд...
Мартинес Сомало, Эдуардо

Мартинес Сомало, Эдуардо

Его Высокопреосвященство кардинал Эдуардо Мартинес Сомало (исп. Eduardo Martinez Somalo; род. 3...
Зенитная установка

Зенитная установка

Зенитная установка — общее название военной техники, предназначенной для ведения огня по воздуш...