Lehmer's totient problem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Question dropshade.png Unsolved problem in mathematics:
Can the totient function of a composite number divide ?
(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.

For every prime number n, we have φ(n) = n − 1 and so in particular φ(n) divides n − 1. D. H. Lehmer conjectured in 1932 that there are no composite numbers with this latter property.[1]

Properties[edit]

  • 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]
  • The number of solutions to the problem less than X is .[4]
  • In 2017, Shen lixing, a Chinese amateur, wrote two C programs and found 21568 Carmichael numbers (max prime factor is 241921) with ω(n) = 14 and found 87 Carmichael numbers with ω(n) = 15 below 1026. None of them is a solution to this problem. According to a previous result from Richard Pinch, http://www.chalcedon.demon.co.uk/rgep/cartable.html, we can say, "n" > 1026. In the web, he misprint 21568 in 1027 column.

References[edit]

  1. ^ Lehmer (1932)
  2. ^ Sándor et al (2006) p.23
  3. ^ Guy (2004) p.142
  4. ^ Sándor et al (2006) p.24
  • Cohen, Graeme L.; Hagis, Peter, jun. (1980). "On the number of prime factors of n if φ(n) divides n−1". Nieuw Arch. Wiskd., III. Ser. 28: 177–185. ISSN 0028-9825. Zbl 0436.10002.
  • 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. Ser. 6 (3): 255–261. ISSN 0028-9825. Zbl 0668.10006.
  • Lehmer, D. H. (1932). "On Euler's totient function". Bulletin of the American Mathematical Society. 38: 745–751. doi:10.1090/s0002-9904-1932-05521-5. ISSN 0002-9904. Zbl 0005.34302.
  • 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". Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Comput. 35: 43–49. ISSN 0138-9491. MR 2894552. Zbl 1240.11005.

External links[edit]