OPEN
This is open, and cannot be resolved with a finite computation.
Is it true that, for any $a\in\mathbb{Z}$, there are infinitely many $n$ such that\[\phi(n) \mid n+a?\]
A conjecture of Graham. Lehmer has conjectured that $\phi(n)\mid n-1$ if and only if $n$ is prime. It is an easy exercise to show that $\phi(n) \mid n$ if and only if $n=2^a3^b$.
This is discussed in problem B37 of Guy's collection
[Gu04].
View the LaTeX source
This page was last edited 30 September 2025.
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #828, https://www.erdosproblems.com/828, accessed 2025-11-16
