Euler-phi function is multiplicative if coprime
This article is about a fact in number theory that has a direct proof using group theory.
The Euler-phi function is multiplicative on coprime natural numbers.
Statement with symbols
For any natural numbers that are coprime to each other, .
coprime positive integers
Proof: Consider a finite cyclic group G of order . Denote by the set of all elements in G that have orders respectively. We will show that .
Define a map by . Since the order of and are coprime, and is abelian, their product must have order , so this map is well-defined. If then , or equivalently, . They are elements of subgroups of coprime orders that must intersect trivially. So, and , the map is injective. Thus, .
Define another map by . If then and . Suppose . Then . Therefore . Similarly, . So, and must have a common divisor which is the order of . Thus, . Hence our map is again injective, so .
Therefore, , as desired.