A remark on Zolotarev’s theorem
Volume 171 / 2023
Abstract
For an odd integer $n \ge 3$ and $a\in \mathbb {Z}$ with $(a,n)=1$, let $$ \mathcal {U}_{a,n}=\biggl \{1\le x\le \frac {n-1}{2}: \{ax\}_n\ge \frac {n+1}{2}\bigg \}, $$ $$\mathcal {I}_{a,n}=\biggl \{(i,j): 1\le i \lt j\le \frac {n-1}{2}\text { and }\|ai\|_n \gt \|aj\|_n\bigg \},$$ where $\{x\}_n$ denotes the least non-negative residue of $x$ modulo $n$ and $$\|x\|_n:=\min \,\{\{x\}_n,n-\{x\}_n\}.$$ We show that $$ |\mathcal {I}_{a,n}|= |\mathcal {U}_{a,n}|\cdot \biggl (\frac {n-1}{2}-|\mathcal {U}_{a,n}| \bigg ). $$ As a consequence, we obtain $$ \mathop {\rm sign}\gamma _{a,n}=\begin {cases} \bigl (\frac {a}{n}\big )&\text {if }n\equiv 1\pmod {4},\\ 1&\text {if }n\equiv 3\pmod {4}, \end {cases} $$ where $\bigl(\frac{\cdot }{\cdot }\bigr)$ denotes the Jacobi symbol and $\gamma _{a,n}$ is the permutation of $\{1,\ldots ,(n-1)/2\}$ defined by $\gamma _{a,n}(x)=\|ax\|_n$.
