For coprime positive integers , Euler's totient function satisfiesThe Chinese remainder theorem gives a bijection from congruence classes modulo to pairs of congruence classes modulo and . A class is a unit modulo exactly when both component classes are units, because being coprime to is equivalent to being coprime to each factor. Counting these pairs proves the identity. The case where a factor is one follows from .
For example, . The coprimality assumption matters: whereas . Thus the Euler totient function is a multiplicative function, rather than a completely multiplicative function.
Articles by others on the same topic
There are currently no matching articles.