Задача Лемера о функции Эйлера

Шаблон:Unsolved Задача Лемера о функции Эйлера задаёт вопрос, существует ли какое-либо составное число n, такое, что функция Эйлера φ(n) делит n − 1. Задача остаётся нерешённой.

Для любого простого числа n мы имеем $φ (n) = n - 1$ , так что $φ (n)$ делит $n - 1$ . Д. Г. Лемер в 1932 высказал гипотезу, что не существует составных чисел с таким свойствомШаблон:Sfn.

Свойства

Лемер показал, что если какое-либо решение n существует, оно должно быть нечётным, свободным от квадратов числом, делящимся на не менее чем на семь различных простых чисел (т.е. $ω (n) ⩾ 7$ ). Такое число должно быть также числом Кармайкла.
В 1980 Коэн и Хагис доказали, что для любого решения n задачи, $n > 1 0^{20}$ и $ω (n) ⩾ 14$ Шаблон:Sfn.
В 1988 Хагис показал, что если 3 делит любое решение n, то $n > 1 0^{1937042}$ и $ω (n) ⩾ 298848$ Шаблон:Sfn.
Число решений задачи, меньших X, равно $O (X^{1 / 2} (\log X)^{3 / 4})$ Шаблон:Sfn.
В 2017 китайский любитель Шень Лисин написал две программы на языке C и нашёл около 21568 чисел Кармайкла (максимальный простой делитель равен 241921) с $ω (n) = 14$ и 87 чисел Кармайкла с $ω (n) = 15$ меньших 10²⁶. Ни одно из них не является решением для проблемы. Согласно предыдущим результатам Ричарда Пинча Шаблон:Wayback мы можем сказать, что $n > 1 0^{26}$ . На сайте он неверно поместил 21568 в столбец 10²⁷.