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
Contents
Definition
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:
.
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. |
divisibility-preserving 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 . |
Summatory function and average value
Summatory function
The summatory function of the Euler phi-function is termed the totient summatory function.
Relation with other arithmetic functions
Similar 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:
.
- .
Inequalities
- : 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.
Dirichlet series
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.
Algebraic significance
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).