HEXAGONbeta

Lehmer's totient problem with fewer than sixteen prime factors

A mix of human-written and AI-generated textHuman understanding: some partsmath.NT — Number Theory

Contributed by Deep Bhattacharjee ↗

Version 1 / Oct 22, 2026 / CC BY 4.0

Abstract

A composite number nn whose totient divides n−1n-1 was known to have at least fourteen prime factors. We prove that it has at least sixteen, at least 1600116001 if (n−1)/φ(n)≥3(n-1)/\varphi(n)\ge3, and more than 10810^8 if 3∣n3\mid n, and that n<22k−7n<2^{2^{k-7}} if nn has kk prime factors. For the companion equation φ(n)∣n+1\varphi(n)\mid n+1 we show that the nine known solutions are the only ones with at most eight prime factors, and that a further solution prime to 33 has at least sixteen. Each statement is reduced by hand to a finite computation, which independent programs carry out. Lehmer's conjecture remains open, and we state the assertion that would settle it.

Provenance statement

Deep Bhattacharjee directed the work. Claude (Anthropic), used through Claude Code, wrote and ran the search programs, wrote the Lean 4 proofs of the statements that do not depend on a search, and drafted text, which the author reviewed and edited. Every statement is proved in the text or reduced by hand to a finite computation; each computation was carried out by two independently written programs (Python and PARI/GP), one of which never factors an integer, and the programs were tested on an equation with known solutions (Appendix A). Lehmer's conjecture is not claimed; Proposition 9.1 states the equivalent assertion. Programs, logs and Lean proofs: release v1.4.0, https://github.com/creelie/eLhmr/releases/tag/v1.4.0.
AI provenance filesAI-PROVENANCE-HEXAGON.md · 2 KB

Tools used

Anthropic
Claude CodeVersion Opus 5.5 Ultracode

References

  1. L. M. Adleman, C. Pomerance, and R. S. Rumely, On distinguishing prime numbers from composite numbers , Ann. of Math. (2) 117 (1983), no. 1, 173--206. doi:10.2307/2006975 (https://doi.org/10.2307/2006975)DOI
  2. R. Baillie and S. S. Wagstaff, Jr., Lucas pseudoprimes , Math. Comp. 35 (1980), no. 152, 1391--1417. doi:10.1090/S0025-5718-1980-0583518-6 (https://doi.org/10.1090/S0025-5718-1980-0583518-6)DOI
  3. W. D. Banks, C. W. Nevans, and C. Pomerance, A remark on Giuga's conjecture and Lehmer's totient problem , Albanian J. Math. 3 (2009), no. 2, 81--85. doi:10.51286/albjm/1245207560 (https://doi.org/10.51286/albjm/1245207560)DOI
  4. D. Bhattacharjee, Lehmer's totient problem with fewer than sixteen prime factors: programs, data and Lean proofs , version 1.4.0, 2026. https://github.com/creelie/eLhmr/releases/tag/v1.4.0link
  5. J. Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria and factorizations of 2m±12^m\pm1 , Math. Comp. 29 (1975), no. 130, 620--647. doi:10.1090/S0025-5718-1975-0384673-1 (https://doi.org/10.1090/S0025-5718-1975-0384673-1)DOI
  6. P. Burcsi, S. Czirbusz, and G. Farkas, Computational investigation of Lehmer's totient problem , Ann. Univ. Sci. Budapest. Sect. Comput. 35 (2011), 43--49. doi:10.71352/ac.35.043 (https://doi.org/10.71352/ac.35.043)DOI
  7. D. Burek and B. Żmija, A new upper bound for numbers with the Lehmer property and its application to repunit numbers , Int. J. Number Theory 15 (2019), no. 7, 1463--1468. doi:10.1142/S1793042119500830 (https://doi.org/10.1142/S1793042119500830)DOI
  8. G. L. Cohen and P. Hagis, Jr., On the number of prime factors of nn if φ(n)∣(n−1)\varphi(n)\mid(n-1) , Nieuw Arch. Wisk. (3) 28 (1980), 177--185.
  9. H. Cohen and H. W. Lenstra, Jr., Primality testing and Jacobi sums , Math. Comp. 42 (1984), no. 165, 297--330. doi:10.1090/S0025-5718-1984-0726006-X (https://doi.org/10.1090/S0025-5718-1984-0726006-X)DOI
  10. R. J. Cook, Bounds for odd perfect numbers , in: Number Theory (Ottawa, 1996), CRM Proc. Lecture Notes 19 , Amer. Math. Soc., Providence, RI, 1999, 67--71.
Show all 37 referencesShow fewer references
  1. D. Coppersmith, N. Howgrave-Graham, and S. V. Nagaraj, Divisors in residue classes, constructively , Math. Comp. 77 (2008), no. 261, 531--545. doi:10.1090/S0025-5718-07-02007-8 (https://doi.org/10.1090/S0025-5718-07-02007-8)DOI
  2. J. Feitsma and W. Galway, Tables of pseudoprimes and related data , https://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html.link
  3. The FLINT team, FLINT: Fast Library for Number Theory , version 3.6.0, https://flintlib.org.link
  4. S. W. Golomb, Sets of primes with intermediate density , Math. Scand. 3 (1955), 264--274. doi:10.7146/math.scand.a-10445 (https://doi.org/10.7146/math.scand.a-10445)DOI
  5. A. Grytczuk and M. Wójtowicz, On a Lehmer problem concerning Euler's totient function , Proc. Japan Acad. Ser. A Math. Sci. 79 (2003), no. 8, 136--138. doi:10.3792/pjaa.79.136 (https://doi.org/10.3792/pjaa.79.136)DOI
  6. R. K. Guy, Unsolved Problems in Number Theory , 3rd ed., Problem Books in Mathematics, Springer, New York, 2004. doi:10.1007/978-0-387-26677-0 (https://doi.org/10.1007/978-0-387-26677-0)DOI
  7. P. Hagis, Jr., On the equation M⋅φ(n)=n−1M\cdot\varphi(n)=n-1 , Nieuw Arch. Wisk. (4) 6 (1988), no. 3, 255--261.
  8. D. R. Heath-Brown, Odd perfect numbers , Math. Proc. Cambridge Philos. Soc. 115 (1994), no. 2, 191--196. doi:10.1017/S0305004100072030 (https://doi.org/10.1017/S0305004100072030)DOI
  9. D. H. Lehmer, On Euler's totient function , Bull. Amer. Math. Soc. 38 (1932), no. 10, 745--751. doi:10.1090/S0002-9904-1932-05521-5 (https://doi.org/10.1090/S0002-9904-1932-05521-5)DOI
  10. H. W. Lenstra, Jr., Divisors in residue classes , Math. Comp. 42 (1984), no. 165, 331--340. doi:10.1090/S0025-5718-1984-0726007-1 (https://doi.org/10.1090/S0025-5718-1984-0726007-1)DOI
  11. The mathlib Community, The Lean mathematical library , in: Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), ACM, New York, 2020, 367--381. doi:10.1145/3372885.3373824 (https://doi.org/10.1145/3372885.3373824)DOI
  12. H. G. Meijer, Sets of primes with intermediate density , Math. Scand. 34 (1974), 37--43. doi:10.7146/math.scand.a-11502 (https://doi.org/10.7146/math.scand.a-11502)DOI
  13. H. L. Montgomery, A note on the large sieve , J. London Math. Soc. 43 (1968), 93--98. doi:10.1112/jlms/s1-43.1.93 (https://doi.org/10.1112/jlms/s1-43.1.93)DOI
  14. H. L. Montgomery and R. C. Vaughan, The large sieve , Mathematika 20 (1973), no. 2, 119--134. doi:10.1112/S0025579300004708 (https://doi.org/10.1112/S0025579300004708)DOI
  15. L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language , in: Automated Deduction -- CADE 28, Lecture Notes in Comput. Sci., Springer, Cham, 2021, 625--635. doi:10.1007/978-3-030-79876-5_37 (https://doi.org/10.1007/978-3-030-79876-5_37)DOI
  16. P. P. Nielsen, An upper bound for odd perfect numbers , Integers 3 (2003), #A14.
  17. M. Norman, A group-theoretical approach to Lehmer's totient problem , preprint, 2021. arXiv:2106.11781 (https://arxiv.org/abs/2106.11781)arXiv
  18. OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences , sequences A050474 and A203966, https://oeis.org, accessed September 2026.link
  19. The PARI Group, PARI/GP , version 2.15.4, Univ. Bordeaux, https://pari.math.u-bordeaux.fr.link
  20. R. G. E. Pinch, A note on Lehmer's totient problem , poster, Seventh Algorithmic Number Theory Symposium (ANTS VII), Berlin, 2006. https://antsmath.org/ANTSVII/Poster/Pinch_Poster3.pdflink
  21. C. Pomerance, On composite nn for which φ(n)∣n−1\varphi(n)\mid n-1, II , Pacific J. Math. 69 (1977), no. 1, 177--186. doi:10.2140/pjm.1977.69.177 (https://doi.org/10.2140/pjm.1977.69.177)DOI
  22. C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to 25⋅10925\cdot10^9 , Math. Comp. 35 (1980), no. 151, 1003--1026. doi:10.1090/S0025-5718-1980-0572872-7 (https://doi.org/10.1090/S0025-5718-1980-0572872-7)DOI
  23. J. Renze, Computational evidence for Lehmer's totient conjecture , Mathematica notebook, Wolfram Library Archive, MathSource item 5483, 2004. https://library.wolfram.com/infocenter/MathSource/5483/link
  24. J. Sorenson and J. Webster, Strong pseudoprimes to twelve prime bases , Math. Comp. 86 (2017), no. 304, 985--1003. doi:10.1090/mcom/3134 (https://doi.org/10.1090/mcom/3134)DOI
  25. A. Stone, Improved upper bounds for odd perfect numbers -- Part I , Integers 24 (2024), #A114. doi:10.5281/zenodo.14547960 (https://doi.org/10.5281/zenodo.14547960)DOI
  26. E. Wong, Computations on normal families of primes , M.Sc. thesis, Simon Fraser University, 1997. https://summit.sfu.ca/_flysystem/fedora/sfu_migrate/7394/b18771816.pdflink
  27. T. Yamada, On Lehmer's problem and related problems , preprint, 2023; also RIMS Kôkyûroku No. 2285. arXiv:2303.16853 (https://arxiv.org/abs/2303.16853)arXiv

Version history

  1. v1Submitted by Deep BhattacharjeeInitial depositCurrentOct 22, 2026