Totient function

From Encyclopedia of Mathematics
Jump to: navigation, search
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 totient function, Euler totient

Another frequently used named for the Euler function $\phi(n)$, which counts a reduced system of residues modulo $n$: the natural numbers $k \in \{1,\ldots,n\}$ that are relatively prime to $n$.

The Carmichael conjecture on the Euler totient function states that if $\phi(x) = m$ for some $m$, then $\phi(y) = m$ for some $y \neq x$; i.e. no value of the Euler function is assumed once. This has now been verified for $x < 10^{1000000}$, [a1].

A natural generalization of the Euler totient function is the Jordan totient function $J_k(n)$, which counts the number of $k$-tuples $(a_1,\ldots,a_k)$, $a_i \in \{1,\ldots,n\}$, such that $\mathrm{hcf}\{n,a_1,\ldots,a_k\} = 1$. Clearly, $J_1 = \phi$. The $J_k$ are multiplicative arithmetic functions.

One has $$ J_k(n) = n^k \prod_{p|n} \left({ 1 - p^{-k} }\right) $$ where $p$ runs over the prime numbers dividing $n$, and $$ J_k(n) = \sum_{d | n} \mu(n/d) d^k $$ where $\mu$ is the Möbius function and $d$ runs over all divisors of $n$. For $k=1$ these formulae reduce to the well-known formulae for the Euler function.

The Lehmer problem on the Euler totient function asks for the solutions of $M.\phi(n) = n-1$, $M \in \mathbb{N}$, [a2]. For some results on this still (1996) largely open problem, see [a3] and the references therein. The corresponding problem for the Jordan totient function (and $k>1$) is easy, [a4]: For $k>1$, $J_k(n) | n^k-1$ if and only if $n$ is a prime number. Moreover, if $n$ is a prime number, then $J_k(n) = n^k-1$.

For much more information on the Euler totient function, the Jordan totient function and various other generalizations, see [a5], [a6].


[a1] A. Schlafly, S. Wagon, "Carmichael's conjecture on the Euler function is valid below $10^{1000000}$" Math. Comp. , 63 (1994) pp. 415–419
[a2] D.H. Lehmer, "On Euler's totient function" Bull. Amer. Math. Soc. , 38 (1932) pp. 745–751
[a3] V. Siva Rama Prasad, M. Rangamma, "On composite $n$ for which $\phi(n)|n-1$" Nieuw Archief voor Wiskunde (4) , 5 (1987) pp. 77–83
[a4] M.V. Subbarao, V. Siva Rama Prasad, "Some analogues of a Lehmer problem on the totient function" Rocky Mount. J. Math. , 15 (1985) pp. 609–620
[a5] R. Sivamarakrishnan, "The many facets of Euler's totient II: generalizations and analogues" Nieuw Archief Wiskunde (4) , 8 (1990) pp. 169–188
[a6] R. Sivamarakrishnan, "The many facets of Euler's totient I" Nieuw Archief Wiskunde (4) , 4 (1986) pp. 175–190
[a7] L.E. Dickson, "History of the theory of numbers I: Divisibility and primality" , Chelsea, reprint (1971) pp. Chapt. V; 113–155
How to Cite This Entry:
Totient function. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article