# How to tell whether function $x^a \mod{b}$ is bijective or not?

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:

1. If $$b$$ is prime and $$a$$ is coprime to $$b-1$$ then $$x^a \mod{b}$$ is bijective.
2. 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!

• Hi, Kandarin, and welcome to Math.StackExchange. I think you're right about the case where $b$ is prime ($x \mapsto x^a$ is an automorphism of the multiplicative group), but the composite case is more complicated. Take a look at $x^3\!\!\!\!\mod 15$. – FredH Feb 23 at 5:39
• The restriction of this map to the group of units is bijective iff $\gcd(a,\phi(b))=1$. I'm not sure about the whole ring. – lhf Feb 23 at 10:17
• About item 2: the map is bijective for $a=3$ and $b=6$ for instance. – lhf Feb 23 at 12:46

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.

• Thank you so much! – Kandarin Feb 23 at 18:05
• If $b$ is a prime power, or even divisible by $p^2$ for any prime $p$, the map cannot be bijective for $a\gt 1$: Let $x = b/p$, then $x^a$ is divisible by $x^2 = b(b/p^2)$, so $x^a \bmod b = 0$. Only squarefree values of $b$ are in question. – FredH Feb 23 at 23:32
• How embarrassing not to have realised that—though I did also have in mind the auxiliary question of when $\ x^a\$ is a bijection on the group of units of the ring. – lonza leggiera Feb 24 at 2:58