Permuting the units mod n

Let n>2 be an integer and a\in(\mathbb Z/n\mathbb Z)^\times. We have a permutation map on (\mathbb Z/n\mathbb Z)^\times given by \pi(a):x\mapsto ax. Then it is easy to see that

\pi:(\mathbb Z/n\mathbb Z)^\times\to S_{\phi(n)}

is an injective homomorphism, where \phi 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 \pi(a) in the disjoint cycle notation. One of the cycles is (1\ a\ a^2 \cdots a^{k-1}), where k is the order of a modulo n. What about the others? In fact, every cycle is of the form (b\ ba\ ba^2\cdots ba^{k-1}) for some b\in(\mathbb Z/n\mathbb Z)^\times. So every cycle has length k=\hbox{ord}_n(a). And the number of cycles is \phi(n)/k.

Let’s look at the sign \varepsilon(\pi(a)) of \pi(a). There are \phi(n)/k cycles each of length k, and each cycle of length k can be written as a product of k-1 transpositions, so

\varepsilon(\pi(a))=\displaystyle (-1)^{(k-1)\phi(n)/k}=(-1)^{\phi(n)/k}\quad(*)

where the last equality is obtained by looking at the cases when k is even/odd (and using the fact that \phi(n) is even).

Remark. (*) is saying that the number of transpositions in \pi(a) has the same parity as the number of disjoint cycles in it.

Hence f=\varepsilon\circ\pi, being a composition of homomorphisms, is a homomorphism from (\mathbb Z/n\mathbb Z)^\times to \{\pm 1\}. It might be interesting to know for which n we get all of \{\pm 1\} as \hbox{im}(f), and for which n we just get the trivial group \{1\}.

Fact.  \hbox{im}(f)=\{\pm 1\} if and only if \phi(n)/\hbox{ord}_n(a) is odd for some a\in(\mathbb Z/n\mathbb Z)^\times.

Corollary. If there exists a\in(\mathbb Z/n\mathbb Z)^\times such that v_2(\hbox{ord}_2(a))=v_2(\phi(n)), then there are exactly \phi(n)/2 such a‘s. (v_2(n) is the largest integer k such that 2^k\mid n.)

Proposition. If n is a power of two other than 2^2=4, then \hbox{im}(f)=\{1\}.

Proof. We want to show that \phi(n)/\hbox{ord}_n(a) is even for each a\in(\mathbb Z/n\mathbb Z)^\times. If n=2^k then the integers coprime to n are precisely the odd integers, so \phi(n)=2^{k-1}. So \hbox{ord}_n(a)=2^j for some j\le k-1. If j<k-1 there is nothing to prove. Otherwise, suppose that j=k-1. This means a is a primitive root modulo n. A well-known theorem says that primitive roots exist only for 2,4,p^k,2p^k for p an odd prime. Hence n must be 2 or 4\square

On the other hand:

Proposition. If there is a primitive root modulo n, then \hbox{im}(f)=\{\pm 1\}.

Proof. Let \phi(n)=2^qm, where m is odd. Let a be a primitive root modulo n. Then \hbox{ord}_n(a^m)=2^q, so \phi(n)/\hbox{ord}_n(a^m)=m is odd, and so f(a^m)=-1. \square

So both cases in fact occur infinitely often.

I don’t know whether it might be possible to completely classify the integers based on \hbox{im}(f), nor do I know what any of this actually means, but perhaps it is something worth pondering.


Leave a comment

Filed under Algebra, Number theory

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s