Lehmer’s Totient Conjecture

Euler's totient satisfies $\varphi(p)=p-1$ for every prime $p$, so the divisibility $\varphi(n)\mid n-1$ holds trivially at primes. In 1932 D. H. Lehmer asked whether this property characterises the primes: if $n>1$ and $\varphi(n)$ divides $n-1$, must $n$ be prime [Lehmer1932Totient]? The conjecture asserts that no composite number passes the test.

A composite counterexample is known to be tightly constrained: it would have to be odd and squarefree, and — since $\varphi(n)\mid n-1$ forces $a^{n-1}\equiv1\pmod n$ for every $a$ coprime to $n$ — it would in particular be a Carmichael number. Cohen and Hagis showed that such an $n$ must have many distinct prime factors [CohenHagis1980], and computational work such as Renze's has excluded counterexamples in very large ranges [Renze1998Lehmer].

The necessary conditions keep strengthening, but they neither exhaust the search space nor yield a contradiction. The conjecture remains open; settling it requires either a composite $n$ with $\varphi(n)\mid n-1$ or a proof that the divisibility forces primality.