Euler totient function

From Number
Revision as of 22:04, 29 January 2014 by Vipul (Talk | contribs)

Jump to: navigation, search
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

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

.

.

.

  • .

Inequalities

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).