Lehmer's problem on the Euler function

Unsolved problems in mathematics : Can the Euler function be a composite number

n

${\ displaystyle n}$ $n$ share

n-1

${\ displaystyle n-1}$ $n-1$ ?

Lehmer's problem about the Euler function asks whether there is any composite number n such that the Euler function φ ( n ) divides n - 1. The problem remains unsolved.

For any prime number n we have $\varphi (n)=n-1$ ${\ displaystyle \ varphi (n) = n-1}$ ${\ displaystyle \ varphi (n) = n-1}$ , so that $\varphi (n)$ ${\ displaystyle \ varphi (n)}$ ${\ displaystyle \ varphi (n)}$ divides $n-1$ ${\ displaystyle n-1}$ $n-1$ . DG Lemer in 1932 expressed the hypothesis that there are no composite numbers with this property ^[1] .

Content

Properties

Lehmer showed that if some solution n exists, it must be an odd number, square-free number, divisible by at least seven different prime numbers (i.e. $\omega (n)\geqslant 7$ ${\ displaystyle \ omega (n) \ geqslant 7}$ ). This number should also be the Carmichael number .
In 1980, Cohen and Hagis proved that for any solution n of the problem, $n>10^{20}$ ${\ displaystyle n> 10 ^ {20}}$ and $\omega (n)\geqslant 14$ ${\ displaystyle \ omega (n) \ geqslant 14}$ ^[2] .
In 1988, Hagis showed that if 3 divides any solution n , then $n>10^{1937042}$ ${\ displaystyle n> 10 ^ {1937042}}$ and $\omega (n)\geqslant 298848$ ${\ displaystyle \ omega (n) \ geqslant 298848}$ ^[3] .
The number of solutions to a problem smaller than X is equal to $O\left({X^{1/2}(\log X)^{3/4}}\right)$ ${\ displaystyle O \ left ({X ^ {1/2} (\ log X) ^ {3/4}} \ right)}$ ^[4] .
In 2017, Chinese amateur Shen Lixing wrote two programs in C and found about 21,568 Carmichael numbers (the maximum prime divisor is 241921) with $\omega (n)=14$ ${\ displaystyle \ omega (n) = 14}$ and 87 Carmichael numbers with $\omega (n)=15$ ${\ displaystyle \ omega (n) = 15}$ less than 10 ²⁶ . None of them is a solution for the problem. According to Richard Pinch's previous results, we can say that $n>10^{26}$ ${\ displaystyle n> 10 ^ {26}}$ . On the site, he incorrectly placed 21568 in column 10 ²⁷ .

Notes

↑ Lehmer, 1932 .
↑ Handbook of number theory, 2006 , p. 23.
↑ Guy, 2004 , p. 142
↑ Handbook of number theory, 2006 , p. 24

Literature

Graeme L. Cohen, Peter Hagis, jun. If φ ( n ) divides n −1 // Nieuw Arch. Wiskd., III. Ser .. - 1980. - T. 28 . - p . 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. - V. 6 , no. 3 - p . 255–261 . - ISSN 0028-9825 .
Lehmer DH On Euler's totient function // Bulletin of the American Mathematical Society . - 1932. - V. 38 . - p . 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. - V. 35 . - pp . 43–49 . - ISSN 0138-9491 .

Links

Weisstein, Eric W. Lehmer's Totient Problem (English) on the Wolfram MathWorld website.

[_47ba5ec86ba61ebb-1] Lehmer, 1932 .

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

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

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