Euler totient function
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-phi function on a natural number , denoted , is defined in the following equivalent ways :
1. as the number of positive integers not greater than that are coprime to .
2. as the number of generators (cyclic elements) in a cyclic group of order .
Every natural number is the sum of Euler-phi function on positive divisors
For any natural number , we have , where the summation runs over all positive divisors of .
Evaluation on prime powers
For any prime and positive integer , the value of Euler-phi function on is given by the formula . This is an immediate application of the previous fact.
Multiplicative if coprime
The Euler-phi function is multiplicative on coprime numbers, that is, if and are coprime, then .
For full proof, see Euler-phi function is multiplicative if coprime.
Knowing the prime factorization of , we can evaluate by repeated applications of the above facts.
However, knowing only the distinct prime factors of the number is sufficient, because the value of Euler-phi function on it is then given by the formula , where here the product is evaluated over all distinct prime factors of .