Namespaces
Variants
Actions

Difference between revisions of "Euler function"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(→‎Comment: better)
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
The arithmetic function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036480/e0364801.png" /> whose value at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036480/e0364802.png" /> is equal to the number of positive integers not exceeding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036480/e0364803.png" /> and relatively prime to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036480/e0364804.png" />. The Euler function is multiplicative, that is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036480/e0364805.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036480/e0364806.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036480/e0364807.png" />. The function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036480/e0364808.png" /> satisfies the relations
+
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036480/e0364809.png" /></td> </tr></table>
+
''Euler's totient function''
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036480/e03648010.png" /></td> </tr></table>
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036480/e03648011.png" /></td> </tr></table>
+
$$\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).
 
It was introduced by L. Euler (1763).
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  K. Chandrasekharan,  "Introduction to analytic number theory" , Springer  (1968)</TD></TR></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>
 +
</table>
  
  
  
 
====Comments====
 
====Comments====
The function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036480/e03648012.png" /> can be evaluated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036480/e03648013.png" />, where the product is taken over all primes dividing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036480/e03648014.png" />, 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]]].
  
 
For a derivation of the asymptotic formula in the article above, as well as of the formula
 
For a derivation of the asymptotic formula in the article above, as well as of the formula
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036480/e03648015.png" /></td> </tr></table>
+
$$\lim_{n\to\infty}\inf\phi(n)\frac{\ln\ln n}{n}=e^{-\gamma},$$
 +
 
 +
where $\gamma$ is the [[Euler constant|Euler constant]], see also [[#References|[a1]]], Chapts. 18.4 and 18.5.
 +
 
 +
====References====
 +
<table>
 +
<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>
 +
</table>
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036480/e03648016.png" /> is the [[Euler constant|Euler constant]], see also [[#References|[a1]]], Chapts. 18.4 and 18.5.
+
====Comment====
 +
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><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  (1979pp. Chapts. 5; 7; 8</TD></TR></table>
+
<table>
 +
<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>
 +
 
 +
[[Category:Number theory]]

Revision as of 21:40, 18 October 2014


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

References

[1] K. Chandrasekharan, "Introduction to analytic number theory" , Springer (1968) MR0249348 Zbl 0169.37502


Comments

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.

References

[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

Comment

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

[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
How to Cite This Entry:
Euler function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Euler_function&oldid=11814
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article