Namespaces
Variants
Actions

Difference between revisions of "Totient function"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (better)
m (→‎References: better)
 
Line 27: Line 27:
 
<TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Schlafly,  S. Wagon,  "Carmichael's conjecture on the Euler function is valid below "  ''Math. Comp.'' , '''63'''  (1994)  pp. 415–419</TD></TR>
 
<TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Schlafly,  S. Wagon,  "Carmichael's conjecture on the Euler function is valid below 10^{1000000}"  ''Math. Comp.'' , '''63'''  (1994)  pp. 415–419</TD></TR>
 
<TR><TD valign="top">[a2]</TD> <TD valign="top">  D.H. Lehmer,  "On Euler's totient function"  ''Bull. Amer. Math. Soc.'' , '''38'''  (1932)  pp. 745–751</TD></TR>
 
<TR><TD valign="top">[a2]</TD> <TD valign="top">  D.H. Lehmer,  "On Euler's totient function"  ''Bull. Amer. Math. Soc.'' , '''38'''  (1932)  pp. 745–751</TD></TR>
<TR><TD valign="top">[a3]</TD> <TD valign="top">  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</TD></TR>
+
<TR><TD valign="top">[a3]</TD> <TD valign="top">  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</TD></TR>
 
<TR><TD valign="top">[a4]</TD> <TD valign="top">  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</TD></TR>
 
<TR><TD valign="top">[a4]</TD> <TD valign="top">  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</TD></TR>
 
<TR><TD valign="top">[a5]</TD> <TD valign="top">  R. Sivamarakrishnan,  "The many facets of Euler's totient II: generalizations and analogues"  ''Nieuw Archief Wiskunde (4)'' , '''8'''  (1990)  pp. 169–188</TD></TR>
 
<TR><TD valign="top">[a5]</TD> <TD valign="top">  R. Sivamarakrishnan,  "The many facets of Euler's totient II: generalizations and analogues"  ''Nieuw Archief Wiskunde (4)'' , '''8'''  (1990)  pp. 169–188</TD></TR>

Latest 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(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: http://encyclopediaofmath.org/index.php?title=Totient_function&oldid=35642
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article