math.NT — Number Theory
A sixteen-prime-factor bound for Lehmer's totient problem and exact prime-completion criteria
We study composite integers for which Euler's totient divides . The finite-search results give at least sixteen distinct prime factors, at least when , and more than when . A solution with prime factors satisfies , and every solution exceeds . For the companion divisibility , the nine known solutions exhaust the cases with at most eight prime factors. For a fixed prime prefix , , the quotient is forced to be and a possible largest prime is uniquely . 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.