Lehmer's totient problem
From HandWiki
Short description: Unsolved problem in mathematics
 |
Unsolved problem in mathematics: Can the totient function of a composite number [math]\displaystyle{ n }[/math] divide [math]\displaystyle{ n-1 }[/math]? (more unsolved problems in mathematics)
|
In mathematics, Lehmer's totient problem asks whether there is any composite number n such that Euler's totient function φ(n) divides n − 1. This is an unsolved problem.
It is known that φ(n) = n − 1 if and only if n is prime. So for every prime number n, we have φ(n) = n − 1 and thus in particular φ(n) divides n − 1. D. H. Lehmer conjectured in 1932 that there are no composite numbers with this property.[1]
History
- Lehmer showed that if any composite solution n exists, it must be odd, square-free, and divisible by at least seven distinct primes (i.e. ω(n) ≥ 7). Such a number must also be a Carmichael number.
- In 1980, Cohen and Hagis proved that, for any solution n to the problem, n > 1020 and ω(n) ≥ 14.[2]
- In 1988, Hagis showed that if 3 divides any solution n, then n > 101937042 and ω(n) ≥ 298848.[3] This was subsequently improved by Burcsi, Czirbusz, and Farkas, who showed that if 3 divides any solution n, then n > 10360000000 and ω(n) ≥ 40000000.[4]
- A result from 2011 states that the number of solutions to the problem less than [math]\displaystyle{ X }[/math] is at most [math]\displaystyle{ {X^{1/2}/(\log X)^{1/2+o(1)}} }[/math].[5]
References
- Cohen, Graeme L.; Hagis, Peter, jun. (1980). "On the number of prime factors of n if φ(n) divides n−1". Nieuw Arch. Wiskd.. III Series 28: 177–185. ISSN 0028-9825.
- Guy, Richard K. (2004). Unsolved problems in number theory (3rd ed.). Springer-Verlag. B37. ISBN 0-387-20860-7.
- Hagis, Peter, jun. (1988). "On the equation M⋅φ(n)=n−1". Nieuw Arch. Wiskd.. IV Series 6 (3): 255–261. ISSN 0028-9825.
- Lehmer, D. H. (1932). "On Euler's totient function". Bulletin of the American Mathematical Society 38 (10): 745–751. doi:10.1090/s0002-9904-1932-05521-5. ISSN 0002-9904.
- Luca, Florian; Pomerance, Carl (2011). "On composite integers n for which [math]\displaystyle{ \varphi(n)\mid n-1 }[/math]". Bol. Soc. Mat. Mexicana 17 (3): 13–21. ISSN 1405-213X. https://www.researchgate.net/publication/265577414.
- Ribenboim, Paulo (1996). The New Book of Prime Number Records (3rd ed.). New York: Springer-Verlag. ISBN 0-387-94457-5.
- Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, eds (2006). Handbook of number theory I. Dordrecht: Springer-Verlag. ISBN 1-4020-4215-9.
- Burcsi, Péter; Czirbusz, Sándor; Farkas, Gábor (2011). "Computational investigation of Lehmer's totient problem". Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Comput. 35: 43–49. ISSN 0138-9491. http://ac.inf.elte.hu/Vol_035_2011/043.pdf.
 |  |
