Euler totient function

From Groupprops
Jump to: navigation, search
This article is about a basic definition in group theory. The article text may, however, contain advanced material.
VIEW: Definitions built on this | Facts about this: (facts closely related to Euler totient function, all facts related to Euler totient function) |Survey articles about this | Survey articles about definitions built on this
VIEW RELATED: Analogues of this | Variations of this | Opposites of this |[SHOW MORE]


The Euler totient function, also known as the Euler-phi function, on a natural number n, denoted \varphi(n), is defined in the following equivalent ways:

  1. as the number of positive integers not greater than n that are coprime to n.
  2. as the number of generators of the cyclic group of order n.


Every natural number is the sum of the Euler totient function on positive divisors

For any natural number n, we have n=\sum_{d|n}\varphi(n), where the summation runs over all positive divisors of n.

Evaluation on prime powers

For any prime p and positive integer k, the value of Euler totient function on p^{k} is given by the formula \varphi(p^{k})=p^{k-1}(p-1). This is an immediate application of the previous fact.

Multiplicative function

The Euler totient function is multiplicative, that is, if m and n are coprime, then \varphi(mn)=\varphi(m)\varphi(n). For full proof, see Euler totient function is multiplicative.

Explicit formula

Knowing the prime factorization of n, we can evaluate \varphi(n) by repeated applications of the above facts.
However, knowing only the distinct prime factors of the number is sufficient, because the value of Euler totient function on it is then given by the formula \varphi(n)=n\prod_{p}(1-\frac1{p}), where here the product is evaluated over all distinct prime factors of n.