# Euler function

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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