Let denote the number of integers such that (Euler’s Phi Function). I read a proof of the following fact about the function proved using group theory; indicating the power ofgroup theory in enumerative combinatorics.
Direct Proof: We shall assume that the reader is aware of the fact that is multiplicative that is . We know that . Let , then
Considering the general case where ,
for every .
Here is a simpler looking group theoretic proof.
There are exactly generators of the subgroup where is a divisor of . Every element of is a generator of exactly one subgroup of .