What conditions must integers $a$, $b$ suffice to make $x^a \mod{b}$ a bijective function?
(I brute force tested out two findings, but not sure whether they are correct or not:
- If $b$ is prime and $a$ is coprime to $b-1$ then $x^a \mod{b}$ is bijective.
- If $b$ is not prime, $x^a \mod{b}$ is not bijective unless $a = 1$.
Not sure how to prove these two findings mathematically)
Any help is much appreciated!
If $\ b\ $ is prime and $\ a\in \mathbb Z\ $, then the function $\ f\ $ defined on $\ \{\,0,1,2, \dots, b-1\,\}$ by $\ f(x) = x^a\ \mathrm{mod}\ b\ $ is indeed bijective if and only if $\ a\ $ is coprime to $\ b-1\ $. Here's a formal proof.
Since $\ f(0) = 0\ $, and the domain of $\ f\ $ is finite, the bijectivity of $\ f\ $ will follow once it's shown to be one-to-one on the non-zero elements of its domain. It's well-known that these elements form a cyclic group of order $\ b-1\ $ under multiplication $\ \mathrm{mod}\ b\ $, so if $\ x\ $ and $\ y\ $ are elements of this group with $\ x^a = y^a\ $, and $\ d\ $ is the order of the group element $\ x\,y^{-1}\ $, then $\ d\, \vert\, b-1 $ and $\ \left(x\,y^{-1}\right)^a = 1\ $, so $\ d\,\vert\,a\ $ also, and is therefore a common divisor of $\ b-1\ $ and $\ a\ $. Thus, if $\ a\ $ and $\ b-1\ $ are coprime, it follows that $\ d=1\ $, and $\ x\,y^{-1}=1\ $, or $\ x=y\ $. So in this case, $\ f\ $ is bijective.
On the other hand, if $\ a\ $ and $\ b-1\ $ are not coprime, then they have a common divisor $\ e > 1\ $. If $\ b-1 = e\,h\ , a = e\,j$, and $\ g\ $ is a generator of the group of units $\ \mathrm{mod}\ b\ $, then $\ x = g^h\ $ is a non-identity element of the group with $\ x^a = g^{hej}=g^{(b-1)j}=1=1^a\ $. Thus $\ f\left(g^h\right) = f(1)\ $ in this case, and $\ f\ $ cannot be a bijection.
If $\ b\ $ is composite, the question is more complicated, as several comments have indicated. As the next step towards the general case, I would suggest tackling the one where $\ b\ $ is a prime power.