In mathematics, Lehmer's totient problem asks whether there is any
composite number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
''n'' such that
Euler's totient function φ(''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
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
''n'', we have φ(''n'') = ''n'' − 1 and thus in particular φ(''n'') divides ''n'' − 1.
D. H. Lehmer 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 {{no footnotes, date=December 2015
In mathematics, a square-free element is an element ''r'' of a unique factorization domain ''R'' that is not divisible by a non-trivial square. This means that every ''s'' such that s^2\mid r is a unit of ''R''.
A ...
, and divisible by at least seven distinct primes (i.e. ''ω(n) ≥ 7''). Such a number must also be a
Carmichael number
In number theory, a Carmichael number is a composite number n, which in modular arithmetic satisfies the congruence relation:
:b^n\equiv b\pmod
for all integers b. The relation may also be expressed in the form:
:b^\equiv 1\pmod.
for all integers ...
.
* In 1980, Cohen and Hagis proved that, for any solution ''n'' to the problem, ''n'' > 10
20 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
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