In mathematics, Lehmer's totient problem asks whether there is any composite number ''n'' such that

Euler's totient function In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...

φ(''n'') divides ''n'' − 1. This is an unsolved problem. It is known that φ(''n'') = ''n'' − 1 if and only if ''n'' is prime. So for every prime number ''n'', we have φ(''n'') = ''n'' − 1 and thus in particular φ(''n'') divides ''n'' − 1.

D. H. Lehmer Derrick Henry "Dick" Lehmer (February 23, 1905 – May 22, 1991), almost always cited as D.H. Lehmer, was an American mathematician significant to the development of computational number theory. Lehmer refined Édouard Lucas' work in the 1930s and ...

conjectured in 1932 that there are no composite numbers with this property.

Properties

* Lehmer showed that if any composite solution ''n'' exists, it must be odd, square-free, and divisible by at least seven distinct primes (i.e. ''ω(n) ≥ 7''). Such a number must also be a Carmichael number. * In 1980, Cohen and Hagis proved that, for any solution ''n'' to the problem, ''n'' > 10²⁰ and ω(''n'') ≥ 14.Sándor et al (2006) p.23 * In 1988, Hagis showed that if 3 divides any solution ''n'', then ''n'' > 10 and ω(''n'') ≥ .Guy (2004) p.142 This was subsequently improved by Burcsi, Czirbusz, and Farkas, who showed that if 3 divides any solution ''n'', then ''n'' > 10 and ω(''n'') ≥ . * The number of solutions to the problem less than

X

is at most

.Luca and Pomerance (2011)

References

* * * * * * * * {{cite journal , zbl=1240.11005, mr = 2894552 , last1=Burcsi , first1=Péter , last2=Czirbusz , first2=Sándor , last3=Farkas , first3=Gábor , title=Computational investigation of Lehmer's totient problem , url=http://ac.inf.elte.hu/Vol_035_2011/043.pdf , journal=Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Comput. , volume=35 , pages=43–49 , year=2011 , issn=0138-9491 Conjectures Unsolved problems in number theory Multiplicative functions