Let be an integer and . We have a permutation map on given by . Then it is easy to see that
is an injective homomorphism, where is Euler’s totient function. This is the key idea in the proof of Cayley’s theorem, but we are going to do something a bit different.
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 .
Let’s look at the sign of . There are cycles each of length , and each cycle of length can be written as a product of transpositions, so
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.