Vtyjkyuk

Here $U(16)$ is set of integers less than 16 that are coprime to it.

We have to prove that mapping $f:xto x^3$ is an automorphism.

Here I am not able to prove that $f$ is onto. Is there a general method for providing proof for surjectivness. I seem to be encountering this a lot.

Hint: A map from a finite set to itself is onto if and only if it is injective, so you can try to show that the kernel of the map is trivial. What are the solutions in $U_16$ of $x^3=1$?

The map $x mapsto x^3$ is surjective because $x=x^9=(x^3)^3$.

The first equality comes $x^8=1$, since $U(16)$ has order $8$.

Therefore, $x mapsto x^3$ is a bijection, since $U(16)$ is finite.

The other answers are very good general ways to proceed. However, your $U(16)$ only contains eight elements. How hard is it to cube eight numbers and reduce them modulo $16$? (That is, never forget that direct computation also works and can be much faster than thinking about structure.)

actually, in $U(16)$, $x longmapsto x^3$ is the reciprocal function to $x longmapsto x^3$ because $(x^3)^3=x^9=x^8.x=1.x=x$ . As it is bijective, it is an automorphism.

In the general case, in $U(n)$, if $p$ is coprime with $varphi(n)$, where $varphi(n)$ is the order of $U(n)$, then $x longmapsto x^p$ is an automorphism, thanks to :

1) Bezout's identity : $ exists (u,v);u>0 / p.u+varphi(n).v=1$.

2) Euler's theorem, stating that : $forall x in U(n), x^varphi(n)=1$

3) Then, $x^p.u+v.varphi(n)=x$, so $x^p.u . (x^varphi(n))^v=x$, so $x^p.u=x$

Then $x longmapsto x^u$ is the reciprocal of $x longmapsto x^p$.