Namespaces
Variants
Actions

Difference between revisions of "Totient function"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (→‎References: better)
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
{{TEX|done}}
 +
 
''Euler totient function, Euler totient''
 
''Euler totient function, Euler totient''
  
Another frequently used named for the [[Euler function|Euler function]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t1100401.png" />, which counts the natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t1100402.png" /> that are relatively prime to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t1100403.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t1100404.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t1100405.png" /> for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t1100406.png" />; i.e. no value of the Euler function is assumed once. This has now been verified for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t1100407.png" />, [[#References|[a1]]].
+
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}$, [[#References|[a1]]].
  
A natural generalization of the Euler totient function is the Jordan totient function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t1100408.png" />, which counts the number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t1100409.png" />-tuples <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004010.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004011.png" />, such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004012.png" />. Clearly, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004013.png" />.
+
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 function]]s.
  
 
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
 +
$$
 +
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.
  
<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/t/t110/t110040/t11004014.png" /></td> </tr></table>
+
The Lehmer problem on the Euler totient function asks for the solutions of $M.\phi(n) = n-1$, $M \in \mathbb{N}$, [[#References|[a2]]]. For some results on this still (1996) largely open problem, see [[#References|[a3]]] and the references therein. The corresponding problem for the Jordan totient function (and $k>1$) is easy, [[#References|[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$.
 
 
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004015.png" /> runs over the prime numbers dividing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004016.png" />, and
 
 
 
<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/t/t110/t110040/t11004017.png" /></td> </tr></table>
 
 
 
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004018.png" /> is the [[Möbius function|Möbius function]] and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004019.png" /> runs over all divisors of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004020.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004021.png" /> these formulas reduce to the well-known formulas for the Euler function.
 
 
 
The Lehmer problem on the Euler totient function asks for the solutions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004023.png" />, [[#References|[a2]]]. For some results on this still (1996) largely open problem, see [[#References|[a3]]] and the references therein. The corresponding problem for the Jordan totient function (and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004024.png" />) is easy, [[#References|[a4]]]: For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004026.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004027.png" /> is a prime number. Moreover, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004028.png" /> is a prime number, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004029.png" />.
 
  
 
For much more information on the Euler totient function, the Jordan totient function and various other generalizations, see [[#References|[a5]]], [[#References|[a6]]].
 
For much more information on the Euler totient function, the Jordan totient function and various other generalizations, see [[#References|[a5]]], [[#References|[a6]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Schlafly,  S. Wagon,  "Carmichael's conjecture on the Euler function is valid below <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004030.png" />"  ''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">[a3]</TD> <TD valign="top">  V. Siva Rama Prasad,  M. Rangamma,  "On composite <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004031.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t110/t110040/t11004032.png" />"  ''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">[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">[a6]</TD> <TD valign="top">  R. Sivamarakrishnan,  "The many facets of Euler's totient I"  ''Nieuw Archief Wiskunde (4)'' , '''4'''  (1986)  pp. 175–190</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  L.E. Dickson,  "History of the theory of numbers" , '''I: Divisibility and primality''' , Chelsea, reprint  (1971)  pp. Chapt. V; 113–155</TD></TR></table>
+
<table>
 +
<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">[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">[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">[a6]</TD> <TD valign="top">  R. Sivamarakrishnan,  "The many facets of Euler's totient I"  ''Nieuw Archief Wiskunde (4)'' , '''4'''  (1986)  pp. 175–190</TD></TR>
 +
<TR><TD valign="top">[a7]</TD> <TD valign="top">  L.E. Dickson,  "History of the theory of numbers I: Divisibility and primality" , Chelsea, reprint  (1971)  pp. Chapt. V; 113–155</TD></TR>
 +
</table>

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=12673
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article