Задача Лемера о функции Эйлера ({g;gcg Lybyjg k srutenn |wlyjg)

Нерешённые проблемы математики: Может ли функция Эйлера составного числа $n$ делить $n-1$?

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

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

Свойства

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

Ссылки

• Weisstein, Eric W. Lehmer's Totient Problem (англ.) на сайте Wolfram MathWorld.