2
$\begingroup$

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?

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I don't think it's open for $k = 1$, unless the existence of infinitely many primes has come into doubt ;-) $\endgroup$ Apr 29, 2021 at 16:52
  • $\begingroup$ @NickMatteo Edited. $\endgroup$ Apr 29, 2021 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.