HEXAGONbeta

A sixteen-prime-factor bound for Lehmer's totient problem and exact prime-completion criteria

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

We study composite integers nn for which Euler's totient divides n−1n-1. The finite-search results give at least sixteen distinct prime factors, at least 1800118001 when (n−1)/φ(n)≥3(n-1)/\varphi(n)\ge3, and more than 10910^9 when 3∣n3\mid n. A solution with kk prime factors satisfies n<22k−7n<2^{2^{k-7}}, and every solution exceeds 103510^{35}. For the companion divisibility φ(n)∣n+1\varphi(n)\mid n+1, the nine known solutions exhaust the cases with at most eight prime factors. For a fixed prime prefix A=∏pA=\prod p, B=∏(p−1)B=\prod(p-1), the quotient is forced to be M=⌈A/B⌉M=\lceil A/B\rceil and a possible largest prime is uniquely q=1+(A−1)/(MB−A)q=1+(A-1)/(MB-A). We derive its exact divisibility, coprimality and valuation consequences, and prove that deleting the largest prime of a hypothetical counterexample cannot yield a smaller Lehmer counterexample. A two-prime factorisation identifies the additional integrality and primality conditions required by a replacement construction. A complete finite construction is proved for every prescribed factor count. Excluding its output at every factor count, or excluding the final prime for every prefix, remains unproved; the full Lehmer conjecture is not resolved.

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 Fable 5.1 Medium

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 depositSupersededOct 22, 2026
  2. v2Submitted by Deep BhattacharjeeSubmitted as a new versionCurrentOct 27, 2026