The desired property holds if and only if $n = 1$ or $n \equiv 2 \pmod{4}$. Let $\sigma_{n,m}$ be the permutation of $\ZZ/n\ZZ$ 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. \begin{lemma} \label{lem:2023B5-2} 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. \end{lemma} \begin{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. \end{proof} 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 $$\ZZ/n\ZZ \cong \ZZ/p^e \ZZ \times \ZZ/k \ZZ.$$ Recall that the group $(\ZZ/p^e \ZZ)^\times$ is cyclic; choose $m \in \ZZ$ reducing to a generator of $(\ZZ/p^e \ZZ)^\times$ and to the identity in $(\ZZ/k\ZZ)^\times$. Then $\sigma_{n,m}$ consists of $k$ cycles (an odd number) of length $p^{e-1}(p-1)$ (an even number) plus some shorter cycles. By Lemma~\ref{lem:2023B5-2}, $\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 $$\ZZ/n\ZZ \cong \ZZ/2\ZZ \times \ZZ/k\ZZ.$$ Then $\sigma_{n,m}$ acts on $\{0\} \times \ZZ/k\ZZ$ and $\{1\} \times \ZZ/k\ZZ$ with the same cycle structure, so every cycle length occurs an even number of times. By Lemma~\ref{lem:2023B5-2}, $\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~\ref{lem:2023B5-2}, $\sigma_{n,m}$ does not have a square root.