Complete residue system proof I was given a proof of this in class, but it does not make sense to me, can someone provide a better proof, or explain the one I have provided, thanks.
Suppose $\gcd(a,n) = 1$, where $a$ and $n$ are natural numbers. Prove that $0$, $a$, $2a$, $3a,\ldots, (n-1)a$, is complete residue system modulo $n$.
Proof given in class:
\begin{align*}
ka &\equiv ra \pmod{n}\\
&\Rightarrow  k \equiv r \pmod{n}\\
&\Rightarrow  \text{$k-r$ divides $n$}\\
&\Rightarrow \text{$k=r$ because $0\leq k\lt n$, $0\leq r\lt n$}
\end{align*}
 A: A complete residue system modulo $n$ is a set of $n$ integers containing a representative element from each congruence class modulo $n$ (see Wikipedia for more details).
A commonly used complete residue system is $\{0,1,\ldots,n-1\}$ where it is easy to see that any two elements are incongruent.
The claim states that if gcd(a,n)=1, then $\{0,a,2a,\ldots,(n-1)a\}$ is a complete residue system modulo $n$.  Since there are exactly $n$ elements in this set, in order to prove the claim, it is sufficient to show that $ka \not\equiv ra \pmod n$ whenever $0 \leq k<r \leq n-1$.
Step 1: $ka \equiv ra \pmod n$ implies $k \equiv r \pmod n$.  While true, I think it should be remarked that we may "divide" by $a$ only because it is comprime to $n$.  In fact, it's not really division, it's multiplication by an integer $b$ such that $ab \equiv 1 \pmod n$ (which can be shown to exist using the Extended Euclidean Algorithm).  So $ka \equiv ra \pmod n$ implies $kab \equiv rab \pmod n$ implies $k \equiv r \pmod n$.
Step 2: $k \equiv r \pmod n$ implies $n$ divides $k-r$.  There's a typo in the OP's statement.  This is by the definition of congruent modulo n.
Step 3: $n$ divides $k-r$ implies $k=r$ because $0 \leq k<r \leq n-1$.  There's some information left out here in the OP's statement.  In order to have $n$ dividing $k-r$ while both $k$ and $r$ are between $0$ and $n-1$, we must have $k=r$ (note that 0 is divisible by n).
A: Hint $\bmod n\!:\, \ a\,$ invertible $\,\Rightarrow\, a\, \{0,1,2,\ldots,n-1\}\, \equiv\, \{0,1,2,\ldots, n-1\}$
i.e. the map $\ x \to a\:x\ $ is a bijection $\bmod n\,$ so it permutes the congruence classes.
