6
$\begingroup$

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?

  • 0
    You can read about Zolotarev's lemma at wikipedia, too: http://en.wikipedia.org/wiki/Zolotarev%27s_lemma2011-09-03

1 Answers 1

7

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})} $

Here is the plan for proving this.

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)