Prove that $0,(m \pmod n)),(2m \pmod n)),...,((n-1)m \pmod n))$ is a permutation of $0,1,2,...,n-1$

Question

I am reading about Quadratic-Residue codes.

Theorem:

Let $m,n$ be two integers bigger than $1$ and $\gcd(m,n)=1$. Then the map $$X_m:\mathbb{F}_q[x]/(x^n-1) \rightarrow \mathbb{F}_q[x]/(x^n-1), a(x) \rightarrowtail a(x^m)$$ is a permutation of $\mathbb{F}_q^n$ if we identify $\mathbb{F}_q^n$ with $\mathbb{F}_q[x]/(x^n-1)$ through the map $$\pi:(f_0,f_1,...,f_{n-1})\rightarrowtail \sum_{i=0}^{n-1}f_ix^i.$$

Proof: Let $f(x)=\sum_{i=0}^{n-1}f_ix^i$, then, we have

$$X_m(f(x))=f(x^m) \pmod{x^n-1}=\sum_{i=0}^{n-1}f_ix^{(mi \pmod{n}))}, \text{why this?}$$

Hence, it is sufficient to show that

$$0,(m \pmod n)),(2m \pmod n)),...,((n-1)m \pmod n))$$ is a permutation of $0,1,2,...,n-1$, as $\gcd(m,n)=1$

---

How proof that $0,(m \pmod n)),(2m \pmod n)),...,((n-1)m \pmod n))$ is a permutation of $0,1,2,...,n-1$, and why proof this proof the theorem?

Answer 1

The map $\{0,\ldots,n-1\}\to \{0,\ldots,n-1\}$, $k\mapsto km\bmod n$ is injective because $k_1m\bmod n=k_2m\bmod n$ means that $n$ divides $(k_1-k_2)m$, and as $\gcd(m,n)=1$, this imlies $n\mid k_1-k_2$. With $0\le k_1,k_2<n$, this is only possible for $k_10=k_2$. In other words, our map is injective. Hence it is also surjective, i.e., a bijection, aka. a permutaion.