Multiplicativity of the Euler totient function
ID: multiplicativity-of-the-euler-totient-function
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.
New to topics? Read the docs here!