1 Введение 2
1.1 История чисел Кармайкла 2
1.2 Существующие результаты 3
1.3 Результаты, полученные в этой работе 4
1.4 Значение полученных результатов 4
1.5 Обозначения 5
2 Главный результат 6
3 Случаи некоторых малых к 17
4 Список литературы 23
1.1 История чисел Кармайкла
Понятие числа Кармайкла неразрывно связано с малой теоремой Ферма - классическим утверждением элементарной теории чисел, возраст которого составляет без малого четыре столетия. Так, в 1640 г. великий французский математик Пьер Ферма в письме своему другу Бернару Френиклю де Бесси сформулировал следующую теорему.
Теорема 1 (Малая теорема Ферма). Для простого р и целого а, не делящегося на р, р | ар 1 - 1.
На протяжении почти трёх столетий оставался открытым вопрос о справедливости обратного утверждения. Первый шаг к его опровержению сделал Пьер Саррюс, доказавший в 1820 г., что 341 | 2341 — 1, тем самым, опровергнув гипотезу для а = 2. В конце XIX века Алвин Корсельт в работе [1] сформулировал критерий, позволяющий установить, верна ли теорема Ферма для числа п, не обязательно явяющегося простым.
Теорема 2 (критерий Корсельта [1]). Если бесквадратное число п таково, что для любого его простого делителя р выполнено р — 1 | п — 1, то
п | an-1 — 1 для любого целого а, взаимно простого с п. (1)
Кроме того, верно и обратное: если верно (1), то число п свободно от квадратов и для любого простого делителя р числа п выполнено р — 1 | п — 1.
К сожалению, Корсельту не удалось привести пример такого числа п. Первым, кто смог справиться с этой задачей, стал Роберт Кармайкл, указавший пример в статье [2]. Поэтому составные числа, для которых справедливо утвержение малой теоремы Ферма, называются числами Кармайкла.
Определение. Числом Кармайкла называется составное число п, такое, что для любого целого а, взаимно простого с п, п | an-1 — 1.
В тот раз Кармайкл ограничился рассмотрением чисел вида п = р1р2р3, где р1,р2,р3 - простые числа. Он привёл четыре примера: 561, 1105, 2821 и 15841.
Теорема 3. Если (561, a)=1, то 561 | а560 — 1. Аналогичное утверждение верно для чисел 1105, 2821 и 15841.
Двумя годами позднее в своей статье [3] он высказал гипотезу, что «этот список (чисел Кармайкла) может быть расширен бесконечно». И действительно, в 1994 году в статье [4] было показано, что существует бесконечно много чисел Кармайкла.
В этом разделе будет предъявлена требуемая арифметическая прогрессия. Идея доказательства её существования основана на следующем наблюдении.
Лемма 1. Для любых чисел a1,... ,an и b1,... ,bn, таких, что (a1,. .. , an) = 1 и (a,, bi) = 1 для любого i, 1 < i < n, найдётся бесконечно много простых чисел р, для которых верно сравнение р = b, (mod a,) для всех i, 1 < i < n.
Доказательство. Немедленно следует из теоремы Дирихле о простых числах и китайской теоремы об остатках. □
Теперь мы сформулируем главный результат работы.
Теорема 6. Существует бесконечно много нечётных составных k вида k = 3q, где q = A + mB - простое число, для которых в множестве {k • 2n + 1,n > 0} не найдётся ни одного числа Кармайкла. Более того, числа A и B могут быть явно вычислены, что даёт возможность эффективной проверки заданного числа k на соответствие критерию.
Напомним классический результат элементарной теории чисел, впервые доказанный Карлом Фридрихом Гауссом.
Теорема 7 (Квадратичный закон взаимности, без доказательства). Если р,г - различные p r (р— 1)(Г— 1)
простые числа, то I — ) • Bl = (—1) 4 .В частности, если р = 1 (mod 8), а r = 3,
/— бз t л (3-1)(r-i) .
то ( — 1 (—1 = ( — 1) 4 — 1
то —) pj ( 1) 1.
Лемма 2. Пусть число N = 3q • 2n + 1 является числом Кармайкла, причём (6,q) = 1.
Тогда N не имеет простых делителей вида р = q • 2Ь + 1, b ^ 3.
Доказательство. Пусть р = q • 2Ь + 1, N = 3q • 2n + 1 и р | N. Так как р = 1 (mod 8), то (—) = (-р) = 1. По свойству символа Лежандра
1 = (-1) = ( -Ал ) = (2Ь) (я А = (q ,
р ) р ) р ) р ) р /
р / р / р / р/ р/
1=(-М—} = (-) R R = (-)- р ) р ) р } р } р } Р/
р/ р / р/ р/ р/ р/
В силу квадратичного закона взаимности, а также того, что р = 1 (mod 8), (—} = 1. Значит, р = 1 (mod 3), то есть, 2Ь • q = 0 (mod 3), что невозможно, так как (6,q) = 1. Лемма доказана. □
Лемма 3. Пусть натуральное число N представимо в виде N = d1d2d—, причём
v2(di - 1) = a, v2(d— - 1) > а + 1, v2(N - 1) > а + 1 для некоторого a ^ 1. Тогда v2(d2 — 1) = a.
Доказательство. Очевидно...
