<s>[INST] For $x: (1 \to b)$ where $a$ & $b$ are co prime, why is $ax \bmod b$ distinct So, out of curiosity, I was wondering why $x (1 \to b)$ where $a$ & $b$ are co prime, why is $ax \bmod b$ distinct.
For example, let $a = 5$, and $b= 8$:
$\begin{array}{c|c|c} 
x & 5x & 5x\bmod 8 \\ \hline
 1 &  5 & 5 \\
 2 & 10 & 2 \\
 3 & 15 & 7 \\
 4 & 20 & 4 \\
 5 & 25 & 1 \\
 6 & 30 & 6 \\
 7 & 35 & 3 \\
 8 & 40 & 0 \\
\end{array}$
As you can see $5x \bmod 8$ is always distinct. Why?
 [/INST] Suppose $ax\equiv ay\pmod{b}$, with $1\le x\le b$ and $1\le y\le b$. Without loss of generality, we can assume $x\ge y$. Then
$$
a(x-y)\equiv0\pmod{b}
$$
that is, $b\mid a(x-y)$; since $a$ and $b$ are coprime, we conclude that
$$
b\mid (x-y)
$$
but $0\le x-y<b$, so we only have one possibility, namely $x-y=0$.
In a slightly different way, we can use Bézout’s identity: find $u$ and $v$ such that $ua+vb=1$. Then
$$
uax=(1-vb)x=x-vbx\equiv x\pmod{b}
$$
Since from $ax\equiv ay\pmod{b}$ we get $uax\equiv uay\pmod{b}$, we conclude $x\equiv y\pmod{b}$.
</s>