Euler totient function
This article defines an arithmetic function or number-theoretic 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
- 1 Definition
- 2 Properties
- 3 Behavior
- 4 Summatory function and average value
- 5 Relation with other arithmetic functions
- 6 Relation with properties of numbers
- 7 Dirichlet series
- 8 Algebraic significance
Let be a natural number. The Euler phi-function 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:
|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.|
|divisibility-preserving function||Yes||If and are natural numbers such that divides , then divides .|
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 .|
Summatory function and average value
The summatory function of the Euler phi-function is termed the totient summatory function.
Relation with other arithmetic functions
- Universal exponent (also called Carmichael function) is the exponent of the multiplicative group modulo . The universal exponent of , usually denoted , divides .
- Dedekind psi-function is similar tothe Euler phi-function, and is defined as:
Relations expressed in terms of Dirichlet products
- : In other words, the Dirichlet product of the Euler phi-function and the all ones function is the identity function:
- : This is obtained by applying the Mobius inversion formula to the previous identity. The Euler phi-function is thus the Dirichlet product of the identity function and the Mobius function:
- : In other words, the Dirichlet product of the Euler phi-function and the divisor count function equals the divisor sum function:
- : Here, is the prime-counting function, and counts the number of primes less than or equal to , while is the prime divisor count function of .
- : Here, is the divisor count function, counting the total number of divisors of .
Relation with properties of numbers
- Prime number: A natural number such that .
- Polygonal number: A natural number such that is a power of , or equivalently, such that the regular -gon is constructible using straightedge and compass.
Further information: Formula for Dirichlet series of Euler phi-function
The Dirichlet series for the Euler phi-function 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.
The Euler phi-function of is important in the following ways:
- It is the number of generators of the cyclic group of order .
- It is the order of the multiplicative group of the ring of integers modulo (in fact, this multiplicative group is precisely the set of generators of the additive group).