Гвоздь в попытки обратить малую теорему Ферма вбит уже давно

[bot]

Найдите m, разложимое в произведение трёх простых чисел, для которого справедливо утвержение:
$a^m - a \equiv 0 \ (mod \ m)$ для любого a.
ЗЫ. Не сомневаюсь, что это давно известно, поэтому прошу воздержаться от ссылок. Задачка не очень сложная.

[maxal]

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

[Sanyok]

Я слышал, что известных чисел Кармайкла очень мало - немного больше 20 штук...

[maxal]

Нет, их очень много известно. Более того, недавно доказали, что их существует бесконечно много.

[Sanyok]

Да??? Я это прочитал в учебнике, по-моему "алгоритмы и структуры данных", в том месте где речь идет об алгоритмах разложения числа на множители... Дома уточню и попробую процитировать... Хотя ничто не стоит на месте, возможно те данные уже устарели..

[bot]

Sanyok писал(а):

Дома уточню и попробую процитировать...

Но-но, ну дайте порешать-то народу!

[maxal]

Бесконечность их числа доказана аж в 1994 году в статье:
Alford, Granville and Pomerance (1994). There are infinitely many Carmichael numbers, Ann. of Math. 140(3), 703–722.

[Sanyok]

Вот, в инете нашел:

Цитата:

Особо плохими для теста Ферма являются так называемые числа Кармайкла. Они обладают следующим свойством: для любого a такого, что (a, n) = 1 верно
$ a^{n -1} = 1 (mod$ n)
Первые три числа Кармайкла таковы: ..... Среди первых 100000000 чисел их всего 255. Лишь недавно (1994 г.) было доказано, что таких чисел бесконечно много.

Так что похоже, не так уж их и много (я имею в виду, на них случайно сложно напороться)... Сами числа умышленно убрал - пусть народ решает! Я как-то написал программку для генерации простых чисел в диапазоне 1..N (алгоритм - решето Эратосфена), так их вообще море оказалось! Кстати, какое бы N я не брал, количество простых чисел получалось примерно 1/10 от N.

[maxal]

Sanyok писал(а):

Так что похоже, не так уж их и много (я имею в виду, на них случайно сложно напороться)...

Для всех достаточно больших n, количество чисел Кармайкла не превосходящих n больше чем $n^{2/7}$.

Sanyok писал(а):

Кстати, какое бы N я не брал, количество простых чисел получалось примерно 1/10 от N.

Простых чисел не превосходящих N примерно равно $\frac{N}{\ln N}$.

[evgeny]

Не совсем ясно что автор имел ввиду. Найди хотя бы одно такое число или описать все.
Последнее сомнительно, т.к. существет пример из 10200 цифр найденный Dubner (ссылки не привожу)

[bot]

Нет, про описание не заикался - просто рассматривал как тренировочную задачу для студентов. А также при необходимости, можно было бы очередному глобалисту-фундаменталисту дать простую ссылку.
А некоторые из последних может быть даже посмотрят на название и откажутся. В это, правда, слабо верится - не переводятся же триссектристы с квадратурщиками и удвоителями куба.