Difference between revisions of "Euler function"
(→Comment: better) |
m (gather references) |
||
Line 13: | Line 13: | ||
It was introduced by L. Euler (1763). | It was introduced by L. Euler (1763). | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
The function can be evaluated by \phi(n)=n\prod_{p|n}(1-p^{-1}), where the product is taken over all primes dividing n, cf. [[#References|[a1]]]. | The function \phi(n) can be evaluated by \phi(n)=n\prod_{p|n}(1-p^{-1}), where the product is taken over all primes dividing n, cf. [[#References|[a1]]]. | ||
Line 27: | Line 19: | ||
\lim_{n\to\infty}\inf\phi(n)\frac{\ln\ln n}{n}=e^{-\gamma}, | \lim_{n\to\infty}\inf\phi(n)\frac{\ln\ln n}{n}=e^{-\gamma}, | ||
− | where \gamma is the [[ | + | where \gamma is the [[Euler constant]], see also [[#References|[a1]]], Chapts. 18.4 and 18.5. |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
D. H. Lehmer asked whether whether there is any composite number n such that \phi(n) divides n-1. This is true of every [[prime number]], and Lehmer conjectured in 1932 that there are no composite numbers with this property: he showed that if any such n exists, it must be odd, square-free, and divisible by at least seven primes. | D. H. Lehmer asked whether whether there is any composite number n such that \phi(n) divides n-1. This is true of every [[prime number]], and Lehmer conjectured in 1932 that there are no composite numbers with this property: he showed that if any such n exists, it must be odd, square-free, and divisible by at least seven primes. | ||
====References==== | ====References==== | ||
<table> | <table> | ||
+ | <TR><TD valign="top">[1]</TD> <TD valign="top"> K. Chandrasekharan, "Introduction to analytic number theory" , Springer (1968) {{MR|0249348}} {{ZBL|0169.37502}}</TD></TR> | ||
+ | <TR><TD valign="top">[a1]</TD> <TD valign="top"> G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapts. 5; 7; 8 {{MR|0568909}} {{ZBL|0423.10001}}</TD></TR> | ||
<TR><TD valign="top">[b1]</TD> <TD valign="top"> D.H. Lehmer, "On Euler's totient function", ''Bulletin of the American Mathematical Society'' '''38''' (1932) 745–751 Zbl 0005.34302. DOI 10.1090/s0002-9904-1932-05521-5</TD></TR> | <TR><TD valign="top">[b1]</TD> <TD valign="top"> D.H. Lehmer, "On Euler's totient function", ''Bulletin of the American Mathematical Society'' '''38''' (1932) 745–751 Zbl 0005.34302. DOI 10.1090/s0002-9904-1932-05521-5</TD></TR> | ||
</table> | </table> | ||
[[Category:Number theory]] | [[Category:Number theory]] |
Revision as of 09:25, 10 November 2023
Euler's totient function
The arithmetic function \phi whose value at n is equal to the number of positive integers not exceeding n and relatively prime to n (the "totatives" of n). The Euler function is a multiplicative arithmetic function, that is \phi(1)=1 and \phi(mn)=\phi(m)\phi(n) for (m,n)=1. The function \phi(n) satisfies the relations
\sum_{d|n}\phi(d)=n,
c\frac{n}{\ln\ln n}\leq\phi(n)\leq n,
\sum_{n\leq x}\phi(n)=\frac{3}{\pi^2}x^2+O(x\ln x).
It was introduced by L. Euler (1763).
The function \phi(n) can be evaluated by \phi(n)=n\prod_{p|n}(1-p^{-1}), where the product is taken over all primes dividing n, cf. [a1].
For a derivation of the asymptotic formula in the article above, as well as of the formula
\lim_{n\to\infty}\inf\phi(n)\frac{\ln\ln n}{n}=e^{-\gamma},
where \gamma is the Euler constant, see also [a1], Chapts. 18.4 and 18.5.
D. H. Lehmer asked whether whether there is any composite number n such that \phi(n) divides n-1. This is true of every prime number, and Lehmer conjectured in 1932 that there are no composite numbers with this property: he showed that if any such n exists, it must be odd, square-free, and divisible by at least seven primes.
References
[1] | K. Chandrasekharan, "Introduction to analytic number theory" , Springer (1968) MR0249348 Zbl 0169.37502 |
[a1] | G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapts. 5; 7; 8 MR0568909 Zbl 0423.10001 |
[b1] | D.H. Lehmer, "On Euler's totient function", Bulletin of the American Mathematical Society 38 (1932) 745–751 Zbl 0005.34302. DOI 10.1090/s0002-9904-1932-05521-5 |
Euler function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Euler_function&oldid=54308