WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

В теории чисел числом Кармайкла (кармайкловым числом, англ. Carmichael number) называется всякое составное число $n$ , которое удовлетворяет сравнению $b^{n-1}\equiv 1{\pmod {n}}$ для всех целых $b$ , взаимно простых с $n$ . Другими словами, числом Кармайкла называется составное число $n$ , которое является псевдопростым числом по каждому основанию $b$ , взаимно простому с $n$ .

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

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

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

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

История открытия

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

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

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

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

Пусть, что $b^{n}\equiv b{\pmod {n}}$ для всех целых $b$ . Сначала докажем, что число $n$ должно быть свободно от квадратов. Предположим, что это не так и $k^{2}\mid n$ ( $k^{2}$ делит $n$ ) для некоторого целого $k>1$ . Пусть $b=k$ , тогда $k^{n}\equiv k{\pmod {n}}$ . Так как $k^{2}\mid n$ , то это соотношение верно по модулю $k^{2}$ , то есть $k^{n}\equiv k{\pmod {k^{2}}}$ , что противоречит выражению $k^{n}\equiv 0{\pmod {k^{2}}}$ . Таким образом, число $n$ свободно от квадратов. Пусть теперь $p$ – простой делитель числа $n$ . Известно, что мультипликативная группа $(\mathbb {Z} /p\mathbb {Z} )^{*}$ кольца вычетов по модулю $p$ , где $p$ – простое, является циклической группой порядка $p-1$ . Пусть $b$ – целое число, такое, что $b{\pmod {p}}$ – генератор группы $(\mathbb {Z} /p\mathbb {Z} )^{*}$ . Так как $b^{n}\equiv b{\pmod {n}}$ , то имеем $b^{n}\equiv b{\pmod {p}}$ , и так как $b$ и $p$ – взаимнопростые числа, то $b^{n-1}\equiv 1{\pmod {p}}$ . Из того, что порядок примитивного элемента $b{\pmod {p}}$ в группе $(\mathbb {Z} /p\mathbb {Z} )^{*}$ равен $p-1$ , следует, что $p-1\mid n-1$ .

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

Из малой теоремы Ферма следует, что если $p$ – простое, а $b$ – целое, то $b^{k}\equiv b{\pmod {p}}$ для любого положительного целого $k$ , такого что $p-1\mid k-1$ . (Пусть $q\cdot (p-1)=(k-1)$ , где $q$ — положительное целое число. Так как $b^{p}\equiv b\cdot b^{p-1}\equiv b{\pmod {p}},b^{p-1}\equiv 1{\pmod {p}}$ , поэтому $b\cdot b^{p-1}\cdot b^{p-1}\cdot \ldots \cdot b^{p-1}\equiv b\cdot b^{q\cdot (p-1)}\equiv b\cdot b^{k-1}\equiv b^{k}\equiv b{\pmod {p}}$ )

Тогда для частного случая $k=n$ мы имеем, что $b^{n}-b$ делится на любой простой делитель числа $n$ , так как $n$ свободно от квадратов, то $b^{n}-b$ делится на $n$ , то есть $b^{n}\equiv b{\pmod {n}}$ . Таким образом теорема Корсельта доказана.

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

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

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

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

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

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

Если $6m+1$ , $12m+1$ , $18m+1$ — простые числа для одного натурального $m$ , то их произведение $M_{3}(m)=(6m+1)(12m+1)(18m+1)$ является числом Кармайкла^[2].

Это условие может быть удовлетворено, только если число $m$ заканчивается цифрами 0, 1, 5 или 6 по основанию 10, то есть $m$ сравнимо с 0 или 1 по модулю 5. Например, для $m=1$ множители равны соответственно $7$ , $13$ и $19$ , а их произведение даёт число Кармайкла 1729.

Обобщение метода Черника

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

M_{k}(m)=(6m+1)(12m+1)\prod _{i=1}^{k-2}(9\cdot 2^{i}m+1),\quad k\geqslant 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$ и $pqr$ – число Кармайкла, то $q<2p^{2}$ и $r<p^{3}$ . Таким образом, количество чисел Кармайкла, получаемых произведением трёх простых множителей, один из которых известен, конечно.

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

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

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

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

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

Кармайкловы числа имеют по меньшей мере три простых положительных множителя. Первые Кармайкловы числа с $k=3,4,5,\ldots$ простыми множителями (последовательность A006931 в OEIS):

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

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

i
1	$41041=7\cdot 11\cdot 13\cdot 41$
2	$62745=3\cdot 5\cdot 47\cdot 89$
3	$63973=7\cdot 13\cdot 19\cdot 37$
4	$75361=11\cdot 13\cdot 17\cdot 31$
5	$101101=7\cdot 11\cdot 13\cdot 101$
6	$126217=7\cdot 13\cdot 19\cdot 73$
7	$172081=7\cdot 13\cdot 31\cdot 61$
8	$188461=7\cdot 13\cdot 19\cdot 109$
9	$278545=5\cdot 17\cdot 29\cdot 113$
10	$340561=13\cdot 17\cdot 23\cdot 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 \left({-k_{1}\left(\log X\log \log X\right)^{\frac {1}{2}}}\right)

для некоторой константы $k_{1}$

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

C(X)<X\exp {\frac {-k_{2}\log {X}\log {\log {\log {X}}}}{\log {\log {X}}}}

для некоторой константы $k_{2}$ . При этом также доказано^[1], что существует бесконечно много чисел Кармайкла, то есть, $\lim _{X\to \infty }C(X)=\infty$ .

В следующей таблице приведены приближённые минимальные значения константы k для значений X = 10ⁿ при разных 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 2 3 W. R. Alford, A. Granville, C. Pomerance (1994). “There are Infinitely Many Carmichael Numbers” (PDF). Annals of Mathematics. 139: 703–722. DOI:10.2307/2118576.
1 2 3 4 C. Pomerance (1993). “Carmichael numbers” (PDF). Nieuw Arch. Wisk.: 199—209.
↑ G Löh, W. Niebuhr (1996). “A new algorithm for constructing large Carmichael numbers” (PDF). Math. Comp. (214): 823–836. Неизвестный параметр |Volume= (предлагается |volume=) (справка на английском)
↑ Richard Pinch. "The Carmichael numbers up to 10^21" (неопр.) (2007).

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии

[:0-1] 1 2 3 W. R. Alford, A. Granville, C. Pomerance (1994). “There are Infinitely Many Carmichael Numbers” (PDF). Annals of Mathematics. 139: 703–722. DOI:10.2307/2118576.

[:1-2] 1 2 3 4 C. Pomerance (1993). “Carmichael numbers” (PDF). Nieuw Arch. Wisk.: 199—209.

[3] G Löh, W. Niebuhr (1996). “A new algorithm for constructing large Carmichael numbers” (PDF). Math. Comp. (214): 823–836. Неизвестный параметр |Volume= (предлагается |volume=) (справка на английском)

[4] Richard Pinch. "The Carmichael numbers up to 10^21" (неопр.) (2007).