Difference between revisions of "Euler totient function"
(→Measures of difference) 

Line 55:  Line 55:  
}  }  
−  ==  +  ==Related arithmetic functions== 
−  ===Summatory  +  ===Summatory functions=== 
−  The  +  The sum of the values of the totient function for all natural numbers up to a given number is termed the [[totient summary function]]. 
−  +  
−  +  
===Similar functions===  ===Similar functions===  
−  +  { class="sortable" border="1"  
−  +  ! Name of arithmetic function !! Description !! Mathematical relation with Euler totient function  
−  +    
−  <math>\psi(n) = n \prod_{pn} \left( 1 + \frac{1}{p}\right)</math>.  +   [[Universal exponent]] (also called Carmichael function) The [[groupprops:exponent of a groupexponent]] of the multiplicative group modulo <math>n</math>. Denoted <math>\lambda(n)</math> <math>\lambda(n)</math> divides <math>\varphi(n)</math>. This is related to the grouptheoretic fact that [[groupprops:exponent divides orderexponent divides order]]. 
+    
+   [[Dedekind psifunction]]  Defined as <math>\psi(n) = n \prod_{pn} \left( 1 + \frac{1}{p}\right)</math>  Structural similarity in definition. Also, <math>\psi(n) \ge \varphi(n)</math> for all <math>n</math>, with equality occurring iff <math>n = 1</math>.  
===Relations expressed in terms of Dirichlet products===  ===Relations expressed in terms of Dirichlet products===  
−  +  Below are some [[Dirichlet product]]s of importance.  
−  +  
−  +  
−  +  
−  +  
−  +  
−  +  
−  +  
−  +  
−  <math>\sum_{dn} \varphi(d) \sigma_0(n/d) = \sigma(n)</math>.  +  { class="sortable" border="1" 
+  ! Statement !! Function !! Value of the Dirichlet product <math>\varphi *</math> the function !! Description !! Statement in ordinary notation !! Proof !! Corollaries  
+    
+   <math>\varphi * U = E</math> <math>U</math>  the function that sends every natural number to 1  <math>E</math>  the function that sends every natural number to itself  <math>\sum_{dn} \varphi(d) = n</math>  Direct combinatorial argument: each summand is the number of elements in <math>\{ 1, \dots, n \}</math> whose gcd with <math>n</math> with <math>n/d</math>.  <math>\varphi = E * \mu</math>, where <math>\mu</math> is the [[Mobius function]]. This follows from the fact that <math>\mu = U^{1}</math>.<br>Also, <math>\varphi * \sigma_1 = E * E</math>, follows from this and <math>\sigma_1 = E * U</math>.  
+    
+   <math>\varphi * \sigma_0 = \sigma_1</math>  <math>\sigma_0<math>  the [[divisor count function]] <math>\sigma = \sigma_1</math>  the [[divisor sum function]]  <math>\sum_{dn} \varphi(d) \sigma_0(n/d) = \sigma(n)</math>  Proof: We have <math>\sigma_0 = U * U</math> and <math>\sigma_1 = E * U</math> by definition. Multiply both sides of the former by <math>\varphi</math> and use associativity to get <math>\varphi * \sigma_0 = (\varphi * U) * U</math>. Use the preceding identity to get <math>\varphi * \sigma_0 = E * U</math>, so <math>\varphi * \sigma_0 = \sigma_1</math>.  
+  }  
−  +  The table of relationships can be conceptualized as follows, where the cell entries are the products of their row and column headers:  
+  { class="sortable" border="1"  
+  ! !! <math>\mu = U^{1}</math> ([[Mobius function]]) !! <math>I</math> (Kronecker delta with 1, identity for Dirichlet product) !! <math>U</math> ([[all ones function]]) !! <math>\sigma_0 = U^2</math> ([[divisor count function]])  
+    
+   <math>E</math> (identity map, sends everything to itself)  <math>\varphi</math>  <math>E</math>  <math>\sigma_1</math>  no name  
+  }  
===Inequalities===  ===Inequalities===  
Revision as of 22:21, 29 January 2014
This article defines an arithmetic function or numbertheoretic function: a function from the natural numbers to a ring (usually, the ring of integers, rational numbers, real numbers, or complex numbers).
View a complete list of arithmetic functions
Contents
Definition
Let be a natural number. The Euler phifunction or Euler totient function of , denoted , is defined as following:
 It is the order of the multiplicative group modulo , i.e., the multiplicative group of the ring of integers modulo .
 It is the number of elements in that are relatively prime to .
In terms of prime factorization
Suppose we have the following prime factorization of :
.
Then, we have:
.
In other words:
.
Properties
Property  Satisfied?  Statement with symbols 

multiplicative function  Yes  If and are relatively prime natural numbers, then . 
completely multiplicative function  No  It is not true for arbitrary natural numbers and that . For instance, if , then whereas is 2. 
divisibilitypreserving function  Yes  If and are natural numbers such that divides , then divides . 
Behavior
High and low points (relatively speaking)
 Primes are high points: We also have for . Equality occurs if and only if is a prime number.
 Primorials are low points: Roughly, the numbers occurring as primorials (products of the first few primes) have the lowest value of relative to , compared with other similarly sized numbers.
Measures of difference
We use the infinitude of primes for arguing about limit superiors. The limits discussed are in the limit as . Note that the last quotient is undefined for .
Measure  Limit superior  Explanation  Limit inferior  Explanation 

1  maximum value of 1 occurs at primes  Consider the sequence of powers 2. , so .  
1  At each prime , value is . Limit is 1 as  0  Consider the sequence of primorials. The corresponding values of are products of the values for the first few primes . The limit of these is the infinite product over all prime . This diverges because the infinite sum of the reciprocals of the primes diverges.  
1  For each prime , the limit is ,which approaches 1.  1  We can show that for every , there exists such that for all . 
Related arithmetic functions
Summatory functions
The sum of the values of the totient function for all natural numbers up to a given number is termed the totient summary function.
Similar functions
Name of arithmetic function  Description  Mathematical relation with Euler totient function  

Universal exponent (also called Carmichael function)  The exponent of the multiplicative group modulo . Denoted  divides . This is related to the grouptheoretic fact that exponent divides order.  
Dedekind psifunction  Defined as  Structural similarity in definition. Also, for all , with equality occurring iff .
Relations expressed in terms of Dirichlet productsBelow are some Dirichlet products of importance.
The table of relationships can be conceptualized as follows, where the cell entries are the products of their row and column headers:
Inequalities
Relation with properties of numbers
Dirichlet seriesFurther information: Formula for Dirichlet series of Euler phifunction The Dirichlet series for the Euler phifunction is given by: . Using the Dirichlet product identity and the fact that Dirichlet series of Dirichlet product equals product of Dirichlet series, we get: . This simplifies to: . This identity holds not just for the formal Dirichlet series, but also for their analytic continuations, and is valid universally for the meromorphic functions. Algebraic significanceThe Euler phifunction of is important in the following ways:
