Invertibility of a function in Z/m - Does what I have written work? Ok, so I know when $(a, m) = 1$, by Euler's Theorem, $a^{\phi(m)} \equiv 1 \mod m$. Since $\phi(323) = 288$, $a^{288} \equiv 1 \mod m$ when $(a, 323) = 1$. However, there are some elements $a$ such that $(a, 323) \not= 1$ and $a^{288} \not\equiv 1 \mod 323$. Since those elements do not have multiplicative inverses in $\mathbb{Z}/323$, how is it working that $x^n$ is invertible? Am I missing something?


Exercise I.8. Prove that $f : \mathbb{Z}/323 \to \mathbb{Z}/323$ given by $f(x) = x^n$ is a bijective map if $(n, 6) = 1$.
Proof. Assume that $(n, 6) = 1$. Then $2 \not\mid n$ and $3 \not\mid n$. Let $f(x) = x^n$. Now by Theorem 9.3, $\phi(323) = \phi(17 \cdot 19) = (17-1)(19-1) = 16 \cdot 18 = 288 = 2^5 \cdot 3^2$. We need $x$ such that $nx \equiv 1 \mod 288$. Since $2 \not\mid n$ and $ \not\mid n$, $(n, 288) = (n, 2^5 \cdot 3^2) = 1$. Then by Lemma 5.2, $nx \equiv 1 \mod 288$ has exactly one solution. That is, $n^{-1}$ exists in $\mathbb{Z}/288$. Then $f^{-1} = x^{n^{-1}}$ since $f^{-1}(f(x)) = f^{-1}(x^n) = (x^n)^{n^{-1}} = x^{n \cdot n^{-1}} \equiv x \mod 323$. Since $f$ is invertible, $f$ is bijective. $\blacksquare$

(Image version)

Note that $f$ being invertible doesn't mean that all elements of $\mathbb{Z} / 323\mathbb{Z}$ are invertible. That $f$ is an invertible map just means that there is an inverse map $g$ such that
$$\begin{align}
f \circ g &= 1 \\
g \circ f &= 1.
\end{align}
$$
That is: $f(g(x)) = x$ for all $x \in \mathbb{Z} / 323\mathbb{Z}$ and $g(f(x)) = x$ for all $\mathbb{Z} / 323\mathbb{Z}$. When we have such a $g$, we usually denote it by $f^{-1}$. So in your case $f(x) = x^{n^{-1}}$ where $n^{-1}$ is the inverse of $n$ in $\mathbb{Z} / 288\mathbb{Z}$
This relies in part on $n$ satisfying $(n, 6) = 1$.
