Lehmers problem

Inom matematiken är Lehmers problem, uppkallad efter D. H. Lehmer, ett problem som frågar om det finns något sammansatt tal n så att φ(n) delar n − 1. Det här är sant för alla primtal, och Lehmer förmodade 1932 att primtalen är de enda lösningarna: han bevisade att om ett sådant n finns måste det vara udda, kvadratfritt och delbar med åtminstone sju primtal (det vill säga ω(n) ≥ 7).

Properties

• Cohen och Hagis bevisade 1980 att n > 10²⁰ och att ω(n) ≥ 14.
• Hagis bevisade 1988 att om 3 delar n är n > 10^1937042 and ω(n) ≥ 298848.
• Antalet lösningar på problemet mindre än X är $O\left({X^{1/2}(\log X)^{3/4}}\right)$.

Källor

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Lehmer's totient problem, 18 mars 2014.

• Cohen, Graeme L.; Hagis, Peter, jun. (1980). ”On the number of prime factors of n if φ(n) divides n−1”. Nieuw Arch. Wiskd., III. Ser. 28: sid. 177–185. ISSN 0028-9825. 
• Guy, Richard K. (2004). Unsolved problems in number theory (3rd). Springer-Verlag. sid. B37. ISBN 0-387-20860-7 
• Hagis, Peter, jun. (1988). ”On the equation M⋅φ(n)=n−1”. Nieuw Arch. Wiskd., IV. Ser. 6 (3): sid. 255–261. ISSN 0028-9825. 
• Lehmer, D. H. (1932). ”On Euler's totient function”. Bulletin of the American Mathematical Society 38: sid. 745–751. ISSN 0002-9904. 
• Ribenboim, Paulo (1996). The New Book of Prime Number Records (3rd). New York: Springer-Verlag. ISBN 0-387-94457-5 
• Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, reds (2006). Handbook of number theory I. Dordrecht: Springer-Verlag. ISBN 1-4020-4215-9 

Externa länkar

• Weisstein, Eric W., "Lehmer's Totient Problem", MathWorld. (engelska)