Lehmer's totient problem with fewer than sixteen prime factors

A composite number n whose totient divides n − 1 was known to have at least fourteen prime factors. We prove that it has at least sixteen, at least 16001 if (n − 1)/φ(n) ≥ 3, and more than 108 if 3 divides n, and that n < 22k−7 if n has k prime factors. For the companion equation φ(n) | 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 3 has at least sixteen. By the large sieve, the number of prime factors of a solution of either equation is at least doubly exponential in the quotient (n ± 1)/φ(n). Each statement is reduced by hand to a finite computation, which independent programs carry out. Lehmer's totient conjecture, that no composite n has φ(n) | n − 1, remains open and is not claimed; the paper states the assertion about finite sets of primes that would settle it. The archive contains the paper (PDF, LaTeX source with the figures as PNG, LaTeX source with the figures as PDF), the programs of every search, each written at least twice independently, their recorded output and factorisation data, and a Lean 4 formalisation with Mathlib of the lemmas, reductions and structure theorems (the exhaustive searches are not formalised). Earlier versions of the programs are archived at doi:10.5281/zenodo.23072268. Version 1.1.0 adds the DOI of this archive (concept DOI 10.5281/zenodo.23243779) to the paper, the README and the citation file. The mathematics is unchanged from version 1.0.0 (doi:10.5281/zenodo.23243780).