# The parity of the permutation $a \mapsto ma \bmod{n}$

I am working on a unique kind of permutations, and would like to know if there is a quick way to know what is the parity of each of them.

Given an integer $n$, I can take any integer $m$ for which $\mathrm{gcd}(m,n)=1$, and then define for each $0 \leq a \leq n-1$, $f(a) \equiv ma \bmod{n}$.

So, given $n$ and $m$, how can I tell what is the parity of the permutation?

-
–  Bill Dubuque May 11 '11 at 20:19
You can read about Zolotarev's lemma at wikipedia, too: en.wikipedia.org/wiki/Zolotarev%27s_lemma –  Martin Sleziak Sep 3 '11 at 7:17

You are asking about the signature of the permutation $\pi_{m,n}: \mathbb Z/n\mathbb Z\to \mathbb Z/n\mathbb Z :x\mapsto [m]x$. The answer for $n$ odd is $$sgn (\pi_{m,n}) =(\frac{m}{n})$$ where $(\frac{m}{n})$ is the Jacobi symbol.
In case $n$ is even you get $$sgn (\pi_{m,n})=(-1)^{(\frac{n}{2}+1)(\frac{m-1}{2})}$$
Step 1 Assume $n$ is a prime $p$. Then the result $sgn (\pi_{m,p}) =(\frac{m}{p})$, where $(\frac{m}{p})$ is just the Legendre symbol, is due to Zolotarev and you can find a proof in the link provided by Bill in his comment to the question. [The linked article states that it is easy to generalize from prime $n$ to odd $n$, but says nothing about even $n$]
Step 2 Prove the general case by noticing that the function $sgn (\pi_{m,n})$ of $m$ and $n$ satisfies exactly the same multiplicative identities as the Jacobi symbol. Details are in this document (in French)