Lehmer's Problem

Do there exist any Composite Numbers $n$ such that $\phi(n)\vert(n-1)$? No such numbers are known. In 1932, Lehmer showed that such an $n$ must be Odd and Squarefree, and that the number of distinct Prime factors $d(7)\geq 7$. This was subsequently extended to $d(n)\geq 11$. The best current results are $n>10^{20}$ and $d(n)\geq 14$ (Cohen and Hagis 1980), if $30\notdiv n$, then $d(n)\geq 26$ (Wall 1980), and if $3\vert n$ then $d(n)\geq 213$ and $n\geq 5.5\times 10^{570}$ (Lieuwens 1970).

References

Cohen, G. L. and Hagis, P. Jr. ``On the Number of Prime Factors of $n$ is $\phi(n)\vert(n-1)$.'' Nieuw Arch. Wisk. 28, 177-185, 1980.

Lieuwens, E. ``Do There Exist Composite Numbers for which $k\phi(M)=M-1$ Holds?'' Nieuw. Arch. Wisk. 18, 165-169, 1970.

Ribenboim, P. The Book of Prime Number Records, 2nd ed. New York: Springer-Verlag, pp. 27-28, 1989.

Wall, D. W. ``Conditions for $\phi(N)$ to Properly Divide $N-1$.'' In A Collection of Manuscripts Related to the Fibonacci Sequence (Ed. V. E. Hoggatt and M. V. E. Bicknell-Johnson). San Jose, CA: Fibonacci Assoc., pp. 205-208, 1980.