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?
 A: This is basically equivalent to saying "you can divide by $a$ (mod $b$)", since these values all being distinct means there's only one solution to $ax\equiv c$ mod $b$.
This is true because if $a$ and $b$ are coprime, there are integers $n,m$ such that $an+bm=1$. Then $anx=x-bmx\equiv x$ (mod $b$). If $ax$ and $ay$ were the same mod $b$, then $anx$ and $any$ would also be the same mod $b$, but since $anx\equiv x$ and $any\equiv y$, $x$ and $y$ must also be the same.
A: 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}$.
A: The Fundmental Theorem of Arithmetic (FTA): For non-zero integers $d,e,f$ if $f$ divides $de$ and $f$ is co-prime to $d$ then $f$ divides $e.$
Let $a, b$ be co-prime positive integers and let $x,x'$ be integers with $0\leq x<x'\leq b-1.$ Suppose  $ax\equiv ax' \pmod b.$ Then $b$ divides $a(x'-x)$ with $b$ co-prime to $a$ and with $x'-x\ne 0.$. So by the FTA, $\;b$ divides $x'-x.$ But $1\leq x'-x\leq (b-1)-0=b-1$ so $b$  cannot divide $x'-x.$  So  supposing $ax\equiv ax'\pmod b$ leads to absurdity.
The FTA is usually presented by first proving that if $f,d$ are non-$0$ co-prime integers then there exist integers $x,y$ with  $xf+yd=1.$ Then $y\cdot \frac {de}{f}=$ $\frac {(yd)e}{f}=$ $\frac {(1-xf)e}{f}=$ $ -xe+\frac {e}{f}\in \mathbb Z,$ so $\frac {e}{f} \in \mathbb Z.$  
