Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
9  
See Zolotarev's Lemma. –  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

1 Answer 1

up vote 7 down vote accepted

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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.