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 2 / 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) along with GPT SOL 6.1 Ultra, used through Claude Code and Codex, 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).

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.5.0, 2026. https://github.com/creelie/eLhmr/releases/tag/v1.5.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 39 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. P. Mandal, D. Bhattacharjee, and U. Bhattacharya, Code, data and Lean proofs for Lehmer's totient problem with fewer than sixteen prime factors , version 2.5.2, Zenodo, 2026. doi:10.5281/zenodo.23171399 (https://doi.org/10.5281/zenodo.23171399)DOI
  12. 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
  13. 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
  14. G. Molnar and G. Singh, Spoof Lehmer factorizations , Integers 26 (2026), #A33, 15 pp. doi:10.5281/zenodo.18714466 (https://doi.org/10.5281/zenodo.18714466)DOI
  15. 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
  16. 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
  17. 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
  18. P. P. Nielsen, An upper bound for odd perfect numbers , Integers 3 (2003), #A14.
  19. M. Norman, A group-theoretical approach to Lehmer's totient problem , preprint, 2021. arXiv:2106.11781 (https://arxiv.org/abs/2106.11781)arXiv
  20. OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences , sequences A050474 and A203966, https://oeis.org, accessed September 2026.link
  21. The PARI Group, PARI/GP , version 2.15.4, Univ. Bordeaux, https://pari.math.u-bordeaux.fr.link
  22. 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
  23. 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
  24. 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
  25. 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
  26. 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
  27. 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
  28. 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
  29. 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