7
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – FredH Feb 23 at 5:39
  • $\begingroup$ 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. $\endgroup$ – lhf Feb 23 at 10:17
  • $\begingroup$ About item 2: the map is bijective for $a=3$ and $b=6$ for instance. $\endgroup$ – lhf Feb 23 at 12:46
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you so much! $\endgroup$ – Kandarin Feb 23 at 18:05
  • 1
    $\begingroup$ 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. $\endgroup$ – FredH Feb 23 at 23:32
  • $\begingroup$ 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. $\endgroup$ – lonza leggiera Feb 24 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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