Let be a cyclic group of order and let be an integer relatively prime to . Prove that the map is surjective. Use Lagrange’s Theorem to prove that the same is true for any finite group of order .

First let be cyclic of order (I.e. ) and let be an integer relatively prime to . Note that since is abelian, is a group homomorphism. There exist integers and such that , or . Now . Since every element of is of the form , is surjective. Since is finite, is a bijection.

Now let be any finite group of order , and an integer relatively prime to with . Note that is a union of cyclic subgroups; in particular, we have . Thus we can consider the mapping restricted to each of these subgroups. By Lagrange’s Theorem, divides for all , so that by the previous half of this problem the restriction is a surjection, and in fact a bijection. Thus is a surjection (hence bijection) on all of .