Lehmer's totient problem: Difference between revisions

Browse history interactively ← Previous edit Next edit →Content deleted Content addedVisual WikitextInline

Revision as of 18:26, 28 November 2022 editJoshuaZ (talk \| contribs)Extended confirmed users, Pending changes reviewers, Rollbackers31,657 edits add improve bound due to Burcsi, Czierbus, Farkas← Previous edit		Revision as of 18:27, 28 November 2022 edit undoJoshuaZ (talk \| contribs)Extended confirmed users, Pending changes reviewers, Rollbackers31,657 editsm →Properties: formattingNext edit →
Line 10:		Line 10:
	* Lehmer showed that if any composite solution ''n'' exists, it must be odd, ], and divisible by at least seven distinct primes (i.e. ''ω(n) ≥ 7''). Such a number must also be a ].		* Lehmer showed that if any composite solution ''n'' exists, it must be odd, ], and divisible by at least seven distinct primes (i.e. ''ω(n) ≥ 7''). Such a number must also be a ].
	* In 1980, Cohen and Hagis proved that, for any solution ''n'' to the problem, ''n'' > 10<sup>20</sup> and ω(''n'') ≥ 14.<ref name="HBI23">Sándor et al (2006) p.23</ref>		* In 1980, Cohen and Hagis proved that, for any solution ''n'' to the problem, ''n'' > 10<sup>20</sup> and ω(''n'') ≥ 14.<ref name="HBI23">Sándor et al (2006) p.23</ref>
	* In 1988, Hagis showed that if 3 divides any solution ''n'' then ''n'' > 10<sup>1937042</sup> and ω(''n'') ≥ 298848.<ref name=Guy142>Guy (2004) p.142</ref> This was subsequently improved by Burcsi, Czirbusz, and Farkas, who showed that if if $n$ is a solution, with $3\|n$, then <math>\omega(n) \geq 4(10^7)(</math> and that <math> n > 10^{\left(36(10^7)\right) }</math> <ref>{{cite journal \|last1=Burcsi, P. , Czirbusz,S., Farkas, G. \|title=Computational investigation of Lehmer's totient problem \|journal=Ann. Univ. Sci. Budapest. Sect. Comput. \|date=2011 \|volume=35 \|page=43-49}}</ref>		* In 1988, Hagis showed that if 3 divides any solution ''n'' then ''n'' > 10<sup>1937042</sup> and ω(''n'') ≥ 298848.<ref name=Guy142>Guy (2004) p.142</ref> This was subsequently improved by Burcsi, Czirbusz, and Farkas, who showed that if if <math>n</math> is a solution, with <math>3\|n</math>, then <math>\omega(n) \geq 4(10^7)(</math> and that <math> n > 10^{\left(36(10^7)\right) }</math> <ref>{{cite journal \|last1=Burcsi, P. , Czirbusz,S., Farkas, G. \|title=Computational investigation of Lehmer's totient problem \|journal=Ann. Univ. Sci. Budapest. Sect. Comput. \|date=2011 \|volume=35 \|page=43-49}}</ref>
	* The number of solutions to the problem less than <math>X</math> is at most <math>{X^{1/2}/(\log X)^{1/2+o(1)}}</math>.<ref name=LP2011>Luca and Pomerance (2011)</ref>		* The number of solutions to the problem less than <math>X</math> is at most <math>{X^{1/2}/(\log X)^{1/2+o(1)}}</math>.<ref name=LP2011>Luca and Pomerance (2011)</ref>

Revision as of 18:27, 28 November 2022

For Lehmer's Mahler measure problem, see Lehmer's conjecture. Unsolved problem in mathematics: Can the totient function of a composite number

n

divide

n-1

? (more unsolved problems in mathematics)

In mathematics, Lehmer's totient problem asks whether there is any composite number 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 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, 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.
In 1988, Hagis showed that if 3 divides any solution n then n > 10 and ω(n) ≥ 298848. This was subsequently improved by Burcsi, Czirbusz, and Farkas, who showed that if if $n$ is a solution, with $3|n$ , then $\omega (n)\geq 4(10^{7})($ and that $n>10^{\left(36(10^{7})\right)}$
The number of solutions to the problem less than $X$ is at most ${X^{1/2}/(\log X)^{1/2+o(1)}}$ .

References

Lehmer (1932)
Sándor et al (2006) p.23
Guy (2004) p.142
Burcsi, P. , Czirbusz,S., Farkas, G. (2011). "Computational investigation of Lehmer's totient problem". Ann. Univ. Sci. Budapest. Sect. Comput. 35: 43-49.{{cite journal}}: CS1 maint: multiple names: authors list (link)
Luca and Pomerance (2011)

Cohen, Graeme L.; Hagis, Peter, jun. (1980). "On the number of prime factors of n if φ(n) divides n−1". Nieuw Arch. Wiskd. III Series. 28: 177–185. ISSN 0028-9825. Zbl 0436.10002.{{cite journal}}: CS1 maint: multiple names: authors list (link)
Guy, Richard K. (2004). Unsolved problems in number theory (3rd ed.). Springer-Verlag. B37. ISBN 0-387-20860-7. Zbl 1058.11001.
Hagis, Peter, jun. (1988). "On the equation M⋅φ(n)=n−1". Nieuw Arch. Wiskd. IV Series. 6 (3): 255–261. ISSN 0028-9825. Zbl 0668.10006.{{cite journal}}: CS1 maint: multiple names: authors list (link)
Lehmer, D. H. (1932). "On Euler's totient function". Bulletin of the American Mathematical Society. 38: 745–751. doi:10.1090/s0002-9904-1932-05521-5. ISSN 0002-9904. Zbl 0005.34302.
Luca, Florian; Pomerance, Carl (2011). "On composite integers n for which $\varphi (n)\mid n-1$ ". Bol. Soc. Mat. Mexicana. 17 (3): 13–21. ISSN 1405-213X. MR 2978700.
Ribenboim, Paulo (1996). The New Book of Prime Number Records (3rd ed.). New York: Springer-Verlag. ISBN 0-387-94457-5. Zbl 0856.11001.
Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, eds. (2006). Handbook of number theory I. Dordrecht: Springer-Verlag. ISBN 1-4020-4215-9. Zbl 1151.11300.
Burcsi, Péter; Czirbusz, Sándor; Farkas, Gábor (2011). "Computational investigation of Lehmer's totient problem" (PDF). Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Comput. 35: 43–49. ISSN 0138-9491. MR 2894552. Zbl 1240.11005.

Categories: