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 editContent deleted Content addedVisualWikitext
Revision as of 11:53, 16 February 2023 editTpreu (talk | contribs)199 editsNo edit summary← Previous edit Latest revision as of 20:08, 8 April 2024 edit undoBD2412 (talk | contribs)Autopatrolled, IP block exemptions, Administrators2,454,835 editsm →History: clean up spacing around commas and other punctuation fixes, replaced: ,S → , S, , → ,Tag: AWB 
(10 intermediate revisions by 9 users not shown)
Line 1: Line 1:
{{Short description|Unsolved problem in mathematics}}
{{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>? (Claimed resolved in a 2023 preprint)}} {{unsolved|mathematics|Can the totient function of a composite number <math>n</math> divide <math>n-1</math>?}}
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> A preprint from February 2023 claims to resolve the conjecture in the positive.<ref name="zriaa23"> 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>
{{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 />


==History== ==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 |pages=43–49}}</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> * 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==
Line 26: Line 17:
* {{cite book |last=Guy | first=Richard K. | authorlink=Richard K. Guy | title=Unsolved problems in number theory | publisher=] |edition=3rd | year=2004 |isbn=0-387-20860-7 | zbl=1058.11001 | at=B37}} * {{cite book |last=Guy | first=Richard K. | authorlink=Richard K. Guy | title=Unsolved problems in number theory | publisher=] |edition=3rd | year=2004 |isbn=0-387-20860-7 | zbl=1058.11001 | at=B37}}
* {{cite journal | zbl=0668.10006 | last=Hagis | first=Peter, jun. | title=On the equation ''M''⋅φ(''n'')=''n''−1 | journal=Nieuw Arch. Wiskd. |series=IV Series | volume=6 | number=3 | pages=255–261 | year=1988 | issn=0028-9825 }} * {{cite journal | zbl=0668.10006 | last=Hagis | first=Peter, jun. | title=On the equation ''M''⋅φ(''n'')=''n''−1 | journal=Nieuw Arch. Wiskd. |series=IV Series | volume=6 | number=3 | pages=255–261 | year=1988 | issn=0028-9825 }}
* {{cite journal | last=Lehmer | first=D. H. | authorlink=Derrick Henry Lehmer | title=On Euler's totient function | journal=] | volume=38 | pages=745–751 | year=1932 | issn=0002-9904 | zbl=0005.34302 | doi=10.1090/s0002-9904-1932-05521-5| doi-access=free }} * {{cite journal | last=Lehmer | first=D. H. | authorlink=Derrick Henry Lehmer | title=On Euler's totient function | journal=] | volume=38 | pages=745–751 | year=1932 | issue=10 | issn=0002-9904 | zbl=0005.34302 | doi=10.1090/s0002-9904-1932-05521-5| doi-access=free }}
* {{cite journal | last1=Luca | first1=Florian | last2=Pomerance | first2=Carl | title=On composite integers ''n'' for which <math>\varphi(n)\mid n-1</math> | journal=Bol. Soc. Mat. Mexicana | volume=17 | number=3 | pages=13–21 | year=2011 | issn=1405-213X | MR=2978700 | url=https://www.researchgate.net/publication/265577414_On_composite_integers_n_for_which_phnn-1 }} * {{cite journal | last1=Luca | first1=Florian | last2=Pomerance | first2=Carl | title=On composite integers ''n'' for which <math>\varphi(n)\mid n-1</math> | journal=Bol. Soc. Mat. Mexicana | volume=17 | number=3 | pages=13–21 | year=2011 | issn=1405-213X | mr=2978700 | url=https://www.researchgate.net/publication/265577414 }}
*{{cite book | last1=Ribenboim | first1=Paulo | authorlink=Paulo Ribenboim | edition=3rd | title=The New Book of Prime Number Records | publisher=] | location=New York | year=1996 | isbn=0-387-94457-5 | zbl=0856.11001 }} *{{cite book | last1=Ribenboim | first1=Paulo | authorlink=Paulo Ribenboim | edition=3rd | title=The New Book of Prime Number Records | publisher=] | location=New York | year=1996 | isbn=0-387-94457-5 | zbl=0856.11001 }}
* {{cite book | editor1-last=Sándor | editor1-first=József | editor2-last=Mitrinović | editor2-first=Dragoslav S. | editor3-last=Crstici | editor3-first=Borislav | title=Handbook of number theory I | location=Dordrecht | publisher=] | year=2006 | isbn=1-4020-4215-9 | zbl=1151.11300 }} * {{cite book | editor1-last=Sándor | editor1-first=József | editor2-last=Mitrinović | editor2-first=Dragoslav S. | editor3-last=Crstici | editor3-first=Borislav | title=Handbook of number theory I | location=Dordrecht | publisher=] | year=2006 | isbn=1-4020-4215-9 | zbl=1151.11300 }}

Latest revision as of 20:08, 8 April 2024

Unsolved problem in mathematics 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} ? (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.

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)}}} .

References

  1. Lehmer (1932)
  2. Sándor et al (2006) p.23
  3. Guy (2004) p.142
  4. 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)
  5. Luca and Pomerance (2011)
Categories: