Misplaced Pages

Lehmer's totient problem: Difference between revisions

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editNext edit →Content deleted Content addedVisualWikitext
Revision as of 10:32, 19 December 2022 editPit142857 (talk | contribs)5 editsm →Properties: number formatting← Previous edit Revision as of 11:53, 16 February 2023 edit undoTpreu (talk | contribs)199 editsNo edit summaryNext edit →
Line 1: Line 1:
{{for|Lehmer's Mahler measure problem|Lehmer's conjecture}} {{for|Lehmer's Mahler measure problem|Lehmer's conjecture}}
{{unsolved|mathematics|Can the totient function of a composite number <math>n</math> divide <math>n-1</math>?}} {{unsolved|mathematics|Can the totient function of a composite number <math>n</math> divide <math>n-1</math>? (Claimed resolved in a 2023 preprint)}}
In mathematics, '''Lehmer's totient problem''' asks whether there is any ] ''n'' such that ] φ(''n'') divides ''n''&nbsp;−&nbsp;1. This is an unsolved problem. In mathematics, '''Lehmer's totient problem''' asks whether there is any ] ''n'' such that ] φ(''n'') divides ''n''&nbsp;−&nbsp;1. This is an unsolved problem.


It is known that φ(''n'') = ''n''&nbsp;−&nbsp;1 if and only if ''n'' is prime. So for every ] ''n'', we have φ(''n'') = ''n''&nbsp;−&nbsp;1 and thus in particular φ(''n'') divides ''n''&nbsp;−&nbsp;1. ] conjectured in 1932 that there are no composite numbers with this property.<ref>Lehmer (1932)</ref> It is known that φ(''n'') = ''n''&nbsp;−&nbsp;1 if and only if ''n'' is prime. So for every ] ''n'', we have φ(''n'') = ''n''&nbsp;−&nbsp;1 and thus in particular φ(''n'') divides ''n''&nbsp;−&nbsp;1. ] conjectured in 1932 that there are no composite numbers with this property.<ref>Lehmer (1932)</ref> A preprint from February 2023 claims to resolve the conjecture in the positive.<ref name="zriaa23">
{{Citation
| last1=Zriaa
| first1=Said
| year = 2023
| arxiv=2302.07368
| title = A new characterization of prime numbers and solution to Lehmer's conjecture on Euler's totient function
| url=https://arxiv.org/abs/2302.07368}}</ref>


<br /> <br />


==Properties== ==History==
* 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>{{val|1937042}}</sup> and ω(''n'') ≥ {{val|298848}}.<ref name=Guy142>Guy (2004) p.142</ref> This was subsequently improved by Burcsi, Czirbusz, and Farkas, who showed that if 3 divides any solution ''n'', then ''n'' > 10<sup>{{val|360000000}}</sup> and ω(''n'') ≥ {{val|40000000}}.<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>{{val|1937042}}</sup> and ω(''n'') ≥ {{val|298848}}.<ref name=Guy142>Guy (2004) p.142</ref> This was subsequently improved by Burcsi, Czirbusz, and Farkas, who showed that if 3 divides any solution ''n'', then ''n'' > 10<sup>{{val|360000000}}</sup> and ω(''n'') ≥ {{val|40000000}}.<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> * A result from 2011 states that 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>
* In an essentially two page preprint<ref name="zriaa23"/> from 2023 Said Zriaa uses elementary properties about primes and Euler's totient function from number theory and elementary symmetric polynomials from algebra to give a short proof of Lehmer's conjecture.


==References== ==References==

Revision as of 11:53, 16 February 2023

For Lehmer's Mahler measure problem, see Lehmer's conjecture. Unsolved problem in mathematics: Can the totient function of a composite number n {\displaystyle n} divide n − 1 {\displaystyle n-1} ? (Claimed resolved in a 2023 preprint) (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. A preprint from February 2023 claims to resolve the conjecture in the positive.


History

  • 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 3 divides any solution n, then n > 10 and ω(n) ≥ 40000000.
  • A result from 2011 states that the number of solutions to the problem less than X {\displaystyle X} is at most X 1 / 2 / ( log ⁡ X ) 1 / 2 + o ( 1 ) {\displaystyle {X^{1/2}/(\log X)^{1/2+o(1)}}} .
  • In an essentially two page preprint from 2023 Said Zriaa uses elementary properties about primes and Euler's totient function from number theory and elementary symmetric polynomials from algebra to give a short proof of Lehmer's conjecture.

References

  1. Lehmer (1932)
  2. ^ Zriaa, Said (2023), A new characterization of prime numbers and solution to Lehmer's conjecture on Euler's totient function, arXiv:2302.07368
  3. Sándor et al (2006) p.23
  4. Guy (2004) p.142
  5. 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)
  6. Luca and Pomerance (2011)
Categories: