Let denote Euler’s totient function and let be a positive integer. Prove that , where ranges over the positive divisors of .
Let denote the (unique) cyclic group of order . Every element of generates a unique (cyclic) subgroup, which is cyclic. Recall that has a unique (cyclic) subgroup of order for each , and that each of these is generated by elements. That is, letting denote the set of generators of , we have where the union is disjoint. Thus .