¿Cómo saber si la función$x^a \mod{b}$ es biyectiva o no?

Question

¿Qué condiciones debe enteros $a$, $b$ suficiente para hacer $x^a \mod{b}$ un bijective función?

(I fuerza bruta probado dos conclusiones, pero no estoy seguro de si son correctas o no:

1. Si $b$ es el primer y $a$ es coprime a $b-1$ entonces $x^a \mod{b}$ es bijective.
2. Si $b$ no es primo, $x^a \mod{b}$ no es bijective menos $a = 1$.

No está seguro de cómo probar estos dos resultados matemáticamente)

Cualquier ayuda se agradece mucho!

Answer 1

Si $\ b\ $ es el primer y $\ a\in \mathbb Z\ $, entonces la función de $\ f\ $ definido en $\ \{\,0,1,2, \dots, b-1\,\}$ por $\ f(x) = x^a\ \mathrm{mod}\ b\ $ es de hecho bijective si y sólo si $\ a\ $ es coprime a $\ b-1\ $. He aquí una prueba formal.

Desde $\ f(0) = 0\ $, y el dominio de $\ f\ $ es finito, el bijectivity de $\ f\ $ va a seguir una vez demostrado ser uno-a-uno sobre la no-cero de los elementos de su dominio. Es bien sabido que estos elementos forman un grupo cíclico de orden $\ b-1\ $ bajo la multiplicación $\ \mathrm{mod}\ b\ $, por lo que si $\ x\ $ e $\ y\ $ son los elementos de este grupo con $\ x^a = y^a\ $, e $\ d\ $ es el orden de los elementos de grupo $\ x\,y^{-1}\ $, a continuación, $\ d\, \vert\, b-1$ e $\ \left(x\,y^{-1}\right)^a = 1\ $, por lo $\ d\,\vert\,a\ $ también, y por lo tanto es un divisor común de a$\ b-1\ $ e $\ a\ $. Por lo tanto, si $\ a\ $ e $\ b-1\ $ son coprime, se deduce que el $\ d=1\ $, e $\ x\,y^{-1}=1\ $o $\ x=y\ $. Así que en este caso, $\ f\ $ es bijective.

Por otro lado, si $\ a\ $ e $\ b-1\ $ no coprime, entonces ellos tienen un común divisor $\ e > 1\ $. Si $\ b-1 = e\,h\ , a = e\,j$, e $\ g\ $ es un generador del grupo de unidades de $\ \mathrm{mod}\ b\ $, a continuación, $\ x = g^h\ $ es un no-elemento de identidad del grupo con $\ x^a = g^{hej}=g^{(b-1)j}=1=1^a\ $. Por lo tanto $\ f\left(g^h\right) = f(1)\ $ en este caso, y $\ f\ $ no puede ser un bijection.

Si $\ b\ $ es compuesto, la cuestión es más complicada, ya que varios de los comentarios han indicado. Como el siguiente paso es el caso general, me permito sugerir la lucha contra el donde $\ b\ $ es una fuente primaria de energía.