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

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

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

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

Свойства

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

Литература

Graeme L. Cohen, Peter Hagis, jun. On the number of prime factors of n if φ(n) divides n−1 // Nieuw Arch. Wiskd., III. Ser.. — 1980. — Т. 28. — С. 177–185. — ISSN 0028-9825.
Richard K. Guy. Unsolved problems in number theory. — 3rd. — Springer-Verlag, 2004. — ISBN 0-387-20860-7.
Peter Hagis, jun. On the equation M⋅φ(n)=n−1 // Nieuw Arch. Wiskd., IV. Ser.. — 1988. — Т. 6, вып. 3. — С. 255–261. — ISSN 0028-9825.
Lehmer D. H. On Euler's totient function // Bulletin of the American Mathematical Society. — 1932. — Т. 38. — С. 745–751. — ISSN 0002-9904. — doi:10.1090/s0002-9904-1932-05521-5.
Paulo Ribenboim. The New Book of Prime Number Records. — 3rd. — New York: Springer-Verlag, 1996. — ISBN 0-387-94457-5.
Handbook of number theory I / József Sándor, Dragoslav S. Mitrinović, Borislav Crstici. — Dordrecht: Springer-Verlag, 2006. — ISBN 1-4020-4215-9.
Péter Burcsi, Sándor Czirbusz, Gábor Farkas. Computational investigation of Lehmer's totient problem // Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Comput.. — 2011. — Т. 35. — С. 43–49. — ISSN 0138-9491.

Ссылки

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_47ba5ec86ba61ebb-1] Lehmer, 1932.

[_61175a4f940845e5-2] Handbook of number theory, 2006, с. 23.

[_6671398b4d6ee219-3] Guy, 2004, с. 142.

[_61175a4f940845e2-4] Handbook of number theory, 2006, с. 24.