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 .

Advertisements