For which odd number $k$ does $\ \varphi(n) \mid n-k \ $ has infinitely many solutions?

Question

The Lehmer-totient problem: For a prime number $\ n\ $ we have $\ \varphi(n)=n-1\ $. In particular, we have $\ \varphi(n) \mid n-1\ $. Is there a composite number $\ n\ $ with $\ \varphi(n)\mid n-1\ $ ?

It is not known if there is any such composite $n$ but may be Lehmer-totient problem is the tip of the iceberg. I was running computations on variation of this problem and I observed that for every small odd $k$ such as $k = 3,5,7,\ldots 25$ there were only a couple of solutions of $\ \varphi(n) \mid n-k\ $ for $n < 10^{10}$. E.g. for $k = 3$, the only solutions so far are $n = 9, 195$ and $5187$. The data suggests that at most there are finitely many solutions for a given odd $k$.

Question: Is there any fixed odd $k > 1$ such that $\ \varphi(n) \mid n-k\ $ has infinitely many solutions?

Answer 1

This is an open conjecture by R. L. Graham (see R. K. Guy, Unsolved problems in Number theory, Second ed., Springer-Verlag, p. 93):

Conjecture: For all positive integers $k$ there are infinitely many $n$ such that $$ ϕ(n)|(n − k) $$ The conjecture has been proved for $k = 0$, $k = 2^a$ for $a> 0$ and for $k = 2^a\cdot 3^b$ with $a,b>0$. For odd $k\ge 3$ the conjecture is still open.