# Difference between revisions of "Totient function"

(LaTeX) |
m (better) |
||

Line 11: | Line 11: | ||

One has | 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 | where $p$ runs over the prime numbers dividing $n$, and |

## Revision as of 10:04, 14 December 2014

*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].

#### References

[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(nm)|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: http://encyclopediaofmath.org/index.php?title=Totient_function&oldid=35642