The Euler Totient Divisibility Problem a Complete Classification

Euler’s totient function φ(n) has been examined for centuries, yet the general condition φ(n) dividing n + a has never been studied in a systematic way. The question is simple: for which integers a does this hold for infinitely many n? The case a = 0 was solved by Lehmer (1932), while a = −1 remains one of the oldest open problems in number theory. This paper gives a comprehensive characterization for all integer values of a. Infinitely many solutions occur when a = −m for integers m satisfying φ(m) | m. For a = 1, solutions exist precisely when n ∈ {1, 2, 3, 15, 255, 65535, 4294967295}, corresponding to k ≤ 5 in the pattern 22k − 1, and the pattern fails for all k ≥ 6 due to the compositeness of the fifth Fermat number. For all other a, computation up to n ≤ 2 × 106 indicates only finitely many solutions. The proof follows from the multiplicative structure of φ, explicit constructions using coprime primes, and direct computational verification. The result provides the first broad description of the totient divisibility condition across integer shifts and expands the context of Lehmer’s original problem.