On Lehmer's problem and related problems

Abstract

We show that if $N\pm 1=M\phi (N)$ with $N\ne 15,255$ composite, then $M<15.76515\log \log \log N$ and $M<16.03235\log \log \omega (N)$, together with similar results for the unitary totient function, Dedekind function, and the sum of unitary divisors.

14 pages (Added arguments in cases $N$, $N_1$, or $\omega (N)$ is small. Our results make no sense when $N_1\le 17$ or $\omega (N)\le 2$. Moreover, our argument does not work when $N_1=21$ in Theorems 1 or $\omega (N)=3$ in Theorems 2 and 4. Indeed, $N=15,255$ satisfy $N+1=2\phi (N)$ but $\log \log \log 15$ and $\log \log \omega (15)$ are negative and $2>21\log \log \omega (255)$)