Lehmer's Totient Problem

Lehmer's totient problem asks if there exist any composite numbers n such that phi(n)|(n-1), where phi(n) is the totient function? No such numbers are known. However, any such an n would need to be a Carmichael number, since for every element b in the integers (mod n), ord(b,n)|phi(n)|n-1, so b^(n-1)=1 (mod n) and n is a Carmichael number.

In 1932, Lehmer showed that such an n must be odd and squarefree, and that the number of distinct prime factors d(n) must satisfy d(n)>=7. This was subsequently extended to d(n)>=11. The best current result is n>10^(22) and d(n)>=14, improving the 10^(20) lower bound of Cohen and Hagis (1980) since there are no Carmichael numbers less than 10^(22) having >=14 distinct prime factors; Pinch). However, even better results are known in the special cases 30n, in which case d(n)>=26 (Wall 1980), and 3|n, in which case d(n)>=213 and n>=5.5×10^(570) (Lieuwens 1970).

See also

Carmichael Number, Lehmer's Mahler Measure Problem, Totient Function

Explore with Wolfram|Alpha


Cohen, G. L. and Hagis, P. Jr. "On the Number of Prime Factors of n is phi(n)|(n-1)." Nieuw Arch. Wisk. 28, 177-185, 1980.Cohen, G. L. and Segal, S. L. "A Note Concerning Those n for which phi(n)+1 Divides n." Fib. Quart. 27, 285-286, 1989.Lieuwens, E. "Do There Exist Composite Numbers for Which kphi(M)=M-1 Holds?" Nieuw Arch. Wisk. 18, 165-169, 1970.Pinch, R. G. E., P. The New Book of Prime Number Records. 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.

Referenced on Wolfram|Alpha

Lehmer's Totient Problem

Cite this as:

Weisstein, Eric W. "Lehmer's Totient Problem." From MathWorld--A Wolfram Web Resource.

Subject classifications