Lehmer's totient problem
In this article we are going to explore in detail Lehmer's totient problem, a topic/person/date that has captured the attention of millions of people around the world. Taking an in-depth approach, we will examine the different aspects related to Lehmer's totient problem, providing detailed information, expert analysis and varied opinions. From its impact on society to its global implications, this article seeks to shed light on a topic/person/date that has generated debate and interest in multiple areas. Through the presentation of relevant data, interviews with experts and a balanced approach, we aim to offer a complete and enriching view on Lehmer's totient problem.
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 asked in 1932 whether there exist 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 X is at most X1/2 / (log X)1/2 + o(1).[5]
References
- ^ Lehmer (1932)
- ^ Sándor et al (2006) p.23
- ^ Guy (2004) p.142
- ^ Burcsi, P., Czirbusz, S., Farkas, G. (2011). "Computational investigation of Lehmer's totient problem". Ann. Univ. Sci. Budapest. Sect. Comput. 35: 43–49.
{{cite journal}}: CS1 maint: multiple names: authors list (link) - ^ Luca and Pomerance (2011)
- 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. Zbl 0436.10002.
{{cite journal}}: CS1 maint: multiple names: authors list (link) - Guy, Richard K. (2004). Unsolved problems in number theory (3rd ed.). Springer-Verlag. B37. ISBN 0-387-20860-7. Zbl 1058.11001.
- Hagis, Peter, jun. (1988). "On the equation M⋅φ(n)=n−1". Nieuw Arch. Wiskd. IV Series. 6 (3): 255–261. ISSN 0028-9825. Zbl 0668.10006.
{{cite journal}}: CS1 maint: multiple names: authors list (link) - 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. Zbl 0005.34302.
- Luca, Florian; Pomerance, Carl (2011). "On composite integers n for which ". Bol. Soc. Mat. Mexicana. 17 (3): 13–21. ISSN 1405-213X. MR 2978700.
- Ribenboim, Paulo (1996). The New Book of Prime Number Records (3rd ed.). New York: Springer-Verlag. ISBN 0-387-94457-5. Zbl 0856.11001.
- Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, eds. (2006). Handbook of number theory I. Dordrecht: Springer-Verlag. ISBN 1-4020-4215-9. Zbl 1151.11300.
- Burcsi, Péter; Czirbusz, Sándor; Farkas, Gábor (2011). "Computational investigation of Lehmer's totient problem" (PDF). Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Comput. 35: 43–49. ISSN 0138-9491. MR 2894552. Zbl 1240.11005.
