# 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 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.