Let be an integer and . We have a permutation map on given by . Then it is easy to see that
Let’s look at in the disjoint cycle notation. One of the cycles is , where is the order of modulo . What about the others? In fact, every cycle is of the form for some . So every cycle has length . And the number of cycles is .
where the last equality is obtained by looking at the cases when is even/odd (and using the fact that is even).
Remark. is saying that the number of transpositions in has the same parity as the number of disjoint cycles in it.
Hence , being a composition of homomorphisms, is a homomorphism from to . It might be interesting to know for which we get all of as , and for which we just get the trivial group .
Fact. if and only if is odd for some .
Corollary. If there exists such that , then there are exactly such ‘s. ( is the largest integer such that .)
Proposition. If is a power of two other than , then .
Proof. We want to show that is even for each . If then the integers coprime to are precisely the odd integers, so . So for some . If there is nothing to prove. Otherwise, suppose that . This means is a primitive root modulo . A well-known theorem says that primitive roots exist only for for an odd prime. Hence must be or .
On the other hand:
Proposition. If there is a primitive root modulo , then .
Proof. Let , where is odd. Let be a primitive root modulo . Then , so is odd, and so .
So both cases in fact occur infinitely often.
I don’t know whether it might be possible to completely classify the integers based on , nor do I know what any of this actually means, but perhaps it is something worth pondering.