La paridad de la permutación $a \mapsto ma \bmod{n}$

Question

Estoy trabajando en una clase única de permutaciones y quisiera saber si hay una forma rápida de saber cuál es la paridad de cada uno de ellos.

Dado un número entero $n$, puedo tomar cualquier número entero $m$de % que $\mathrm{gcd}(m,n)=1$ y a continuación definir cada $0 \leq a \leq n-1$, $f(a) \equiv ma \bmod{n}$.

Por lo tanto, dado el $n$ y $m$, ¿cómo puedo saber lo que es la paridad de la permutación?

Answer 1

Usted está preguntando acerca de la firma de la permutación $\pi_{m,n}: \mathbb Z/n\mathbb Z\to \mathbb Z/n\mathbb Z :x\mapsto [m]x$. La respuesta de $n$ es impar $$sgn (\pi_{m,n}) =(\frac{m}{n}) $$ donde $ (\frac{m}{n})$ es el símbolo de Jacobi.

En el caso de $n$ es incluso consigue $$sgn (\pi_{m,n})=(-1)^{(\frac{n}{2}+1)(\frac{m-1}{2})} $$

Aquí está el plan para probar esto.

Paso 1 Suponga $n$ es un primer $p$. A continuación, el resultado $sgn (\pi_{m,p}) =(\frac{m}{p})$ donde $(\frac{m}{p})$ es sólo el símbolo de Legendre, es debido a Zolotarev y usted puede encontrar una prueba en el enlace proporcionado por el proyecto de Ley en su comentario a la pregunta. [El artículo vinculado afirma que es fácil de generalizar a partir de prime $n$ a un extraño $n$, pero no dice nada acerca aun $n$]

Paso 2 Probar el caso general, haciendo notar que la función de $sgn (\pi_{m,n})$ $m$ $n$ satisface exactamente la misma multiplicativo identidades como el símbolo de Jacobi. Los detalles están en este documento (en francés)