# 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: (factscloselyrelated to Euler totient function, all facts related to Euler totient function) |Survey articles about this | Survey articles about definitions built on thisVIEW RELATED: Analogues of this | Variations of this | Opposites of this |[SHOW MORE]

## Contents

## Definitions

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 .

## Facts

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

## Explicit formula

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 .