Putnam 2023, Problem B-5

Determine which positive integers \( n \) have the following property: For all integers \( m \) that are relatively prime to \( n \), there exists a permutation \( \pi: \{1, 2, \ldots, n\} \to \{1, 2, \ldots, n\} \) such that \( \pi(\pi(k)) \equiv mk \pmod{n} \) for all \( k \in \{1, 2, \ldots, n\} \).

Solution:
The desired property holds if and only if $n = 1$ or $n \equiv 2 \pmod{4}$.

Let $\sigma_{n,m}$ be the permutation of $\mathbb{Z}/n\mathbb{Z}$ induced by multiplication by $m$; the original problem asks for which $n$ does $\sigma_{n,m}$ always have a square root. For $n = 1$, $\sigma_{n,m}$ is the identity permutation and hence has a square root.

We next identify when a general permutation admits a square root.

**Lemma 1.** A permutation $\sigma$ in $S_n$ can be written as the square of another permutation if and only if for every even positive integer $m$, the number of cycles of length $m$ in $\sigma$ is even.

*Proof.* We first check the "only if" direction. Suppose that $\sigma = \tau^2$. Then every cycle of $\tau$ of length $m$ remains a cycle in $\sigma$ if $m$ is odd, and splits into two cycles of length $m/2$ if $m$ is even.

We next check the "if" direction. We may partition the cycles of $\sigma$ into individual cycles of odd length and pairs of cycles of the same even length; then we may argue as above to write each partition as the square of another permutation. $\square$

Suppose now that $n > 1$ is odd. Write $n = p^e k$ where $p$ is an odd prime, $k$ is a positive integer, and $\gcd(p, k) = 1$. By the Chinese remainder theorem, we have a ring isomorphism
$$\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/p^e\mathbb{Z} \times \mathbb{Z}/k\mathbb{Z}.$$

Recall that the group $(\mathbb{Z}/p^e\mathbb{Z})^\times$ is cyclic; choose $m \in \mathbb{Z}$ reducing to a generator of $(\mathbb{Z}/p^e\mathbb{Z})^\times$ and to the identity in $(\mathbb{Z}/k\mathbb{Z})^\times$. Then $\sigma_{n,m}$ consists of $k$ cycles (an odd number) of length $p^e-1$ (an even number) plus some shorter cycles. By Lemma 1, $\sigma_{n,m}$ does not have a square root.

Suppose next that $n \equiv 2 \pmod{4}$. Write $n = 2k$ with $k$ odd, so that
$$\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/k\mathbb{Z}.$$
Then $\sigma_{n,m}$ acts on $\{0\} \times \mathbb{Z}/k\mathbb{Z}$ and $\{1\} \times \mathbb{Z}/k\mathbb{Z}$ with the same cycle structure, so every cycle length occurs an even number of times. By Lemma 1, $\sigma_{n,m}$ has a square root.

Finally, suppose that $n$ is divisible by 4. For $m = -1$, $\sigma_{n,m}$ consists of two fixed points (0 and $n/2$) together with $n/2 - 1$ cycles (an odd number) of length 2 (an even number). By Lemma 1, $\sigma_{n,m}$ does not have a square root.