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 ![]() ![]() ![]() |
completely multiplicative function | No | It is not true for arbitrary natural numbers ![]() ![]() ![]() ![]() ![]() ![]() |
divisibility-preserving function | Yes | If ![]() ![]() ![]() ![]() ![]() ![]() |
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).
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. ![]() ![]() |
![]() |
1 | At each prime ![]() ![]() ![]() |
0 | Consider the sequence of primorials. The corresponding values of ![]() ![]() ![]() ![]() ![]() |
![]() |
1 | For each prime ![]() ![]() |
1 | We can show that for every ![]() ![]() ![]() ![]() |
Initial values
![]() |
Prime factorization | Totient function ![]() |
![]() ![]() |
![]() ![]() ![]() ![]() |
Universal exponent ![]() |
![]() |
---|---|---|---|---|---|---|
1 | empty | 1 | 0 | 1 | 1 | 1 |
2 | 2 | 1 | 1 | 1/2 | 1 | 1 |
3 | 3 | 2 | 1 | 2/3 | 2 | 1 |
4 | ![]() |
2 | 2 | 1/2 | 2 | 1 |
5 | 5 | 4 | 1 | 4/5 | 4 | 1 |
6 | ![]() |
2 | 4 | 1/3 | 2 | 1 |
7 | 7 | 6 | 1 | 6/7 | 6 | 1 |
8 | ![]() |
4 | 4 | 1/2 | 2 | 1 |
9 | ![]() |
6 | 3 | 2/3 | 6 | 1 |
Prime ![]() |
![]() |
![]() |
1 | ![]() |
![]() |
1 |
Power ![]() |
![]() |
![]() |
![]() |
1/2 | ![]() ![]() ![]() |
2 if ![]() |
Power ![]() ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
1 |
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 ![]() ![]() |
![]() ![]() |
Dedekind psi-function | Defined as ![]() |
Structural similarity in definition. Also, ![]() ![]() ![]() |
Relations expressed in terms of Dirichlet products
Below are some Dirichlet products of importance.
Statement | Function | Description | Value of the Dirichlet product ![]() |
Description | Statement in ordinary notation | Proof | Corollaries |
---|---|---|---|---|---|---|---|
![]() |
![]() |
the function that sends every natural number to 1 | ![]() |
the function that sends every natural number to itself | ![]() |
Direct combinatorial argument: each summand is the number of elements in ![]() ![]() ![]() |
![]() ![]() ![]() Also, ![]() ![]() |
![]() |
![]() |
the divisor count function | ![]() |
the divisor sum function | ![]() |
We have ![]() ![]() ![]() ![]() ![]() ![]() |
The table of relationships can be conceptualized as follows, where the cell entries are the products of their row and column headers. Note that the rows can each be deduced from one another:
![]() |
![]() |
![]() |
![]() | |
---|---|---|---|---|
![]() |
no name | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
no name |
![]() |
![]() |
![]() |
no name | no name |
Inequalities
Nature of bound (upper bound or lower) | Formula | Arithmetic functions used | Explanation | Asymptotic implication |
---|---|---|---|---|
lower | ![]() |
![]() ![]() ![]() ![]() |
Any prime less than or equal to ![]() ![]() ![]() |
![]() ![]() ![]() |
upper | ![]() |
![]() ![]() |
With the exception of 1, any number in ![]() ![]() ![]() |
Nothing specifically, but it does show that for non-primes, there is a relatively sharp demarcation between ![]() ![]() |
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.